快速排序（算法导论）

小鱼儿 2022-06-15 12:57 259阅读 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);
        }
    
    }

仅仅修改了partition的实现方式，感觉第一版更加容易理解。C和java真的不是一种思维方式，看着这过程化的语言难受（算是我的牢骚吧）。