排序算法6：快速排序（QuickSort）

蔚落 2021-09-28 22:18 307阅读 0赞

## 排序算法：快速排序(QuickSort) ##

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：

`快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。`

## 1. 算法步骤 ##

1.  从数列中挑出一个元素，称为 “基准”（pivot）;
2.  重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3.  递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

## 2、 动图展示 ##

![在这里插入图片描述][20190604202643796.gif]

## 3、Code实现：java ##

package com.sort;
    
    
    /** * 递归实现 * @ClassName: QuickSortDemo * @Description: TODO * @Author yunfeng * @Date 2019-06-05 * @Version V1.0 **/
    public class QuickSortDemo2 { 
        public static void main(String[] args) throws Exception { 
            int [] arr = { 3,2,1,5,1,6,7,-1,2,0};
            QuickSortDemo2.quickSort(arr,0,arr.length-1);
            for(int i=0;i<arr.length;i++){ 
                int num = arr[i];
                System.out.println("num = " + num);
            }
        }
    
    
    
        private static void quickSort(int[] arr,int left,int right) { 
    
            int pivot = (left + right) /2;
            int i = left;
            int j = right;
            int pivotValue = arr[pivot];
    
            while(i<j){ 
                while (arr[i] < pivotValue){ 
                    i++;
                }
                while (arr[j] > pivotValue){ 
                    j--;
                }
                if(i<=j){ 
                    swap(arr,i,j);
                    i++;
                    j--;
                }
            }
            if(left < j){ 
                quickSort(arr,left,j);
            }
            if(i < right){ 
                quickSort(arr,i,right);
            }
    
        }
    
    
    
        private static void swap(int[] arr, int i, int j) { 
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
    }

package com.sort;
    
    import java.util.Arrays;
    
    /** * 递归实现 * @ClassName: QuickSortDemo * @Description: TODO * @Author yunfeng * @Date 2019-06-05 * @Version V1.0 **/
    public class QuickSortDemo{ 
        public static void main(String[] args) throws Exception { 
            int [] arr = { 3,2,1,5,1,6,7,-1,2,0};
            int [] arr2 = QuickSortDemo.sort(arr);
            for(int i=0;i<arr2.length;i++){ 
                int num = arr2[i];
                System.out.println("num = " + num);
            }
        }
    
    
        public static int[]  sort(int[] sourceArray) throws Exception { 
            // 对 arr 进行拷贝，不改变参数内容
            int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    
            return quickSort(arr, 0, arr.length - 1);
        }
        
    
        private static int[] quickSort(int[] arr, int left, int right) { 
            //当排序的数组，右边的指针大于左边指针，也就是不能进行分别排序的时候退出递归
            if (left < right) { 
                //按基准值排序区分，获取基准值坐标
                int partitionIndex = partition(arr, left, right);
                //对小于基准值左边的数组进行快速排序
                quickSort(arr, left, partitionIndex - 1);
                //对大于基准值右边的数组进行快速排序
                quickSort(arr, partitionIndex + 1, right);
            }
            return arr;
        }
    
        /** * 按基准值的进行排序，小的在左边，大的在右边，最后返回分隔的区域 * 比如 3,2,1,5,1,6,7,-1,2,0 按基准排序后为 0 2 1 1 -1 2 3 5 6 7 基准索引为3的下标6 * @param arr * @param left * @param right * @return */
        private static int partition(int[] arr, int left, int right) { 
            // 设定基准值（pivot）
            int pivot = left;
            int index = pivot + 1;
            for (int i = index; i <= right; i++) { 
                if (arr[i] < arr[pivot]) { 
                    swap(arr, i, index);
                    index++;
                }
            }
            swap(arr, pivot, index - 1);
            return index - 1;
        }
    
        private static void swap(int[] arr, int i, int j) { 
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
    }

[20190604202643796.gif]: /images/20210923/1cc4cb5a8e934c2c9c6972ce170f7431.png