【算法】快速排序 QuickSort ---java实现

快速排序

算法思想

快速排序是使用分治递归的思想,他的每一次排序就是:在序列中选取一个标准值,将待排序列划分为比标准值大的和比标准值小的两半,然后再将这两半分别再选取各自的标准值,再次划分.直到最后的待排序列小到无法划分(长度为1),那么肯定满足每个序列段,肯定比前一个序列段大,比后一个序列段小.得到排序的最终结果.

步骤

1. 确定待排序列的范围,
2. 选定标准值(一般选该范围中第一个数据)
3. 将这个范围的所有值与标准值比较,得到一个序列,序列前端比标准值小,后端比标准值大(具体算法看一下代码,我第一次看这个算法也很懵,看了很多遍才看懂)如图所示

4. 将标准值前,后的序列段,分别再次使用快速排序,直到划分完的序列段只剩下一个值.

注意点

• 时间复杂度：

  1. 最好：O(n log2 n)
  2. 最坏：O(n^2)
  3. 平均：O(n log2 n)

• 空间复杂度：O(n log2 n)

• 稳定性：不稳定

实验代码

public static int[] quickSort(int[] arr) {quickSort(arr,0,arr.length-1);return arr;}public static void quickSort(int[] arr, int start, int end) {//选定中值if (start >= end) {return;}//使用中值将数组分为两半int left = start;int right = end;int temp = arr[left];while (left < right) {while (left < right && arr[right] >= temp) {right--;}arr[left] = arr[right];while (left < right && arr[left] <= temp) {left++;}arr[right] = arr[left];}arr[left] = temp;//将分为两半的数组再次递归本方法,直到最后的start,end重合时,quickSort(arr, start, left-1);quickSort(arr,left+1,end);// 此时每一段划分出来的数组段都是符合划分原则(前面小于后面),总体看整个数组就是有序的}