首页 > itarticle > 快速排序

快速排序

admin 10月 29, 2020 0

最近学习算法，从一些经典的排序算法开始。

这篇讲的是我对快速排序的一些心得

来源百度百科：

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

思路：

在数组中找到一个节点，比它小的放在节点左边，比它大的放在节点右边。一趟下来，比节点小的在左边，比节点大的在右边。
不断执行这个操作

代码实现思路：

用递归，支点取中间。使用S和E表示数组的开始和末尾。找到大于（小于）支点的数，随后交换
递归S到支点前一个元素j（方法同上）
递归支点后一个元素i到E（方法同上）

//快速排序
public static void quickSort(int[] array,int S,int E){
         int i=S;//指向开头
         int j=E;//指向结尾

         int pivot=array[(i+j)/2];//支点

        while(i<=j){
            while(pivot>array[i]){
                i++;//寻找比支点大的数
            }
            while(pivot<array[j]){
                j--;//寻找比支点小的数
            }
            if(i<=j){
                int temp=array[i];
                array[i]=array[j];
                array[j]=temp;
                i++;
                j--;
            }
            //“左边”再做排序，直到左边剩下一个数(递归出口)
            if(i<E){
                quickSort(array,i,E);
            }
            //“右边”再做排序，直到右边剩下一个数(递归出口)
            if(j>S){
                quickSort(array,S,j);
            }
        }
    }

参考资料：

[]: https://segmentfault.com/a/1190000014008568