快速排序（算法导论）-蒲公英云

快速排序（算法导论）

小鱼儿 2022-06-15 12:57 305阅读 0赞

本算法翻译自算法导论第三版（中文版）第7章170（有兴趣的可以看看，我感觉这本书还是跟晦涩的，可能我也没多读几次的原因）；

1、快速排序介绍
快速排序是一种在实际排序应用中最好的选择，因为他平均的性能非常好，它的期望复杂度是O(nlgn)，快速排序也使用了分治的思想
2操作思路
（1）分解
首先先将问题分解成子问题。
（2）解决
递归调用快速排序对各个子问题进行求解。
（3）合并
无需合并，而归并排序需要进行合并。
伪代码
这段代码主要是为了分解子问题
而解决子问题的快速排序在PARTITION中

QUCIKSORT(A,p,r)
 if p < r
   q=PARTITION(A,p,r)
   QUICKSORT(A,p,r)
   QUICKSORT(A,p,r)
PARTITION(A,p,r)
  x=A[r];
  i=p-1;
  for j=p to r-1
     if A[j]<=x
        i=i+1
        exchange A[j] with A[i]
  exchange A[i+1] with A[end]
  return i+1;

我的java实现
代码一：

import java.util.Arrays;
public class QuickSortTest { 
    private int[] element;
    public QuickSortTest(int[] e) {
        element = e;
    }
    public static void main(String[] args) {
        int[] array = { 2,8,7,1,3,5,6,4 };
        QuickSortTest quick = new QuickSortTest(array);
        quick.sort();
        System.out.println("result"+quick);
    }
    public void sort() {
        quickSort(element, 0, element.length-1);
    }
    private void quickSort(int[] array, int start, int end) {
        if(start<end){
            int loc=partition(array,start,end);  
            quickSort(array,start,loc-1);
            quickSort(array,loc+1,end);
        }
    }
    private int partition(int[] array, int start, int end) {
        System.out.println("开始于"+start+" 终于"+end);
        int x=array[end];  
        /* * 此处用i j两个变量进行记录需要交换的位置 * j采用 if判断 出比x小的位置 * i那么 留下来的默认就比x大 */
        int i =start-1;
        for(int j=start;j<end;j++){
            if(array[j]<=x){        
                i++;
                swap(array,i,j);    
                System.out.println("交换后："+toString());
            }
        }
        //交换基准点
        System.out.println("交换基准点"+array[i+1]+" "+array[end]);
        swap(array,i+1,end);
        System.out.println("某次交换结果："+toString());
        return i+1;
    }
    /**交换i和j的值*/
    private void swap(int[] array,int i,int j){
        System.out.println("交换"+array[i]+" "+array[j]);
        int temp = array[i];
        array[i]=array[j];
        array[j]=temp;
    }
    public String toString(){
        return Arrays.toString(element);
    }
}

代码二采用数据结构书(严蔚敏版)上实现的

import java.util.Arrays;
public class QuickSortTest {
    private int[] element;
    public QuickSortTest(int[] e) {
        element = e;
    }
    public static void main(String[] args) {
        int[] array = { 49, 38, 65, 97, 76, 13, 27 };
        // int[] array = { 2,8,7,1,3,5,6,4 };
        QuickSortTest quick = new QuickSortTest(array);
        quick.sort();
        System.out.println("result" + quick);
    }
    public void sort() {
        quickSort(element, 0, element.length - 1);
    }
    private void quickSort(int[] array, int start, int end) {
        if (start < end) {
            int loc = partition2(array, start, end);
            quickSort(array, start, loc - 1);
            quickSort(array, loc + 1, end);
        }
    }
    private int partition2(int[] array, int i, int j) {
        int key = array[i]; // 将第一个值作为基准值
        while (i < j) {
            while (i < j && key <= array[j])
                j--; // j向左移 直到找到比key小的值
            if (i < j) {      //此处不保证会引起的问题 上一步可能是i>=j所引起的跳出，而不是key<=array 所引起的
                array[i++] = array[j]; // 交换值 每次交换的时候虽然会覆盖但是不会造成数据的丢失
                // 因为key记录了一个位置
                System.out.println(i - 1 + " " + j);
                System.out.println("左侧交换较小值" + this);
            }
            while (i < j && key > array[i])
                i++;
            if (i < j) {
            if(i>=j)System.out.println(i+" "+j+"错误测试2");
                array[j--] = array[i];
                System.out.println(i + " " + (j+1));
                System.out.println("右侧交换较大值" + this);
            }
        }
        array[i] = key;
        System.out.println(this);
        return i;
    }
    public String toString() {
        return Arrays.toString(element);
    }
}