快速排序( Quicksort ）是对冒泡排序算法的一种改进。 02快速排序.mp4

算法思路

快速排序算法的排序流程如下︰

  • 1.先从数列中取出一个数作为基准数。
  • 2 .分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。·
  • 3.再对左右区间重复第二步，直到各区间只有一个数。

一趟快速排序的算法是:
1 ）设置两个变量i、j，排序开始的时候:i=0， j=N-1;
2 ）以第一个数组元素作为基准数，赋值给pivot，即pivot=A[0]=A[i];
3 ）由后向前搜索(j—)，找到第一个小于pivot的值A[i]，将A[i]和Ai]的值交换;
4 ）由前向后搜索(i++)，找到第一个大于pivot的A[i]，将A[i]和A[j]的值交换;
5 ）重复第3、4步，直到i==j;
image.png
经过第1趟排序，数组被划分为两个区，5左边是小于5的(2,3,0.1.4}，Flag右边是大于Flag的6,7,9,10,8)。我们再分别对这两个区进行递归操作，直至每个组里只剩下1个数字，排序完成!

代码实现

  1. public class quickSort {
  2.     public static void main(String[] args){
  3.         int[] arr = {5,3,7,6,4,1,0,2,9,10,8};
  4.         quickSort(arr,0,arr.length-1);
  5.         System.out.println(Array.toString(arr));
  6.     }
  8.     public static void swap(int[] arr, int i, int j)
  9.     {
  10.         int temp = arr[i];
  11.         arr[i] = arr[j];
  12.         arr[j] = temp;
  13.     }
  15.     public static void quickSort(int[] arr ,int low ,int high)
  16.     {
  17.         if(low < high)
  18.         {
  19.             int i = low;
  20.             int j = high;
  22.             while(i<j)
  23.             {
  24.                 //从后向前
  25.                 while(i<j && arr[j]>arr[i])
  26.                 {
  27.                     j--;
  28.                 }
  29.                 //交换
  30.                 swap(arr,i,j);
  31.                 //从前向后
  32.                 while(i<j && arr[i]<=arr[j])
  33.                 {
  34.                     i++;
  35.                 }
  36.                 //交换
  37.                 swap(arr,i,j);
  38.             }
  39.             //递归的进行左右两部分的快排
  40.             quickSort(arr,low,j-1);//前面部分
  41.             quickSort(arr,low,j+1);//后面部分
  42.         }
  43.     }
  44. }

排序稳定性

如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变，通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的;快速排序是不稳定的排序算法。

时间复杂度:O(n log2n)

快速排序的一次划分算法从两头交替搜索，直到low和high重合，因此其时间复杂度是O(n);而整个快速排序算法的时间复杂度与划分的趟数有关。
理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样个算法的时间复杂度为o(nlog2n)。

最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)。
为改善最坏情况下的时间性能，可采用其他方法选取中间数。通常采用“三者值取中”方法，可以证明，快速排序的平均时间复杂度也是o(nlog2n)。因此，该排序方法被认为是目前最好的一种内部排序方法。

三数取中

在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。