排序算法之快速排序！

快速排序的基本思想：

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小。

  • 则可分别对这两部分记录继续进行排序，以达到整个序列有序。

先从数列中取出一个数作为基准数。

分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

再对左右区间重复第二步，直到各区间只有一个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class QuickSort {
    public static void quickSort(int[]arr,int low,int high){
         if (low < high) {     
             int middle = getMiddle(arr, low, high);     
             quickSort(arr, low, middle - 1);//递归左边            
             quickSort(arr, middle + 1, high);//递归右边   
          }  
    }
    public static int getMiddle(int[] list, int low, int high) {     
        int tmp = list[low];    
        while (low < high) {     
            while (low < high && list[high] >= tmp) {//大于关键字的在右边
                high--;     
            }     
            list[low] = list[high];//小于关键字则交换至左边   
            while (low < high && list[low] <= tmp) {//小于关键字的在左边
                low++;     
            }     
            list[high] = list[low];//大于关键字则交换至左边   
        }     
       list[low] = tmp;           
       return low;                   
    } 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class QuickSort {
 
  public static void quickSort(int data[], int left, int right) {
 
    int base = data[left]; // 基准数，取序列的第一个
    int ll = left; // 表示的是从左边找的位置
    int rr = right; // 表示从右边开始找的位置
    while (ll < rr) {
      // 从后面往前找比基准数小的数
      while (ll < rr && data[rr] >= base) {
        rr--;
      }
      if (ll < rr) { // 表示是找到有比之大的
        int temp = data[rr];
        data[rr] = data[ll];
        data[ll] = temp;
        ll++;
      }
      while (ll < rr && data[ll] <= base) {
        ll++;
      }
      if (ll < rr) {
        int temp = data[rr];
        data[rr] = data[ll];
        data[ll] = temp;
        rr--;
      }
    }
    // 肯定是递归 分成了三部分,左右继续快排，注意要加条件不然递归就栈溢出了
    if (left < ll)
      quickSort(data, left, ll - 1);
    if (ll < right)
      quickSort(data, ll + 1, right);
  }
}

优化点：

基本的快速排序选取第一个或最后一个元素作为基准。

  • 但是，这是一直很不好的处理方法。

如果数组已经有序时，此时的分割就是一个非常不好的分割。

因为每次划分只能使待排序序列减一，此时为最坏情况，快速排序沦为冒泡排序，时间复杂度为O(n^2)。

三数取中：

一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。

举例：待排序序列为：8 1 4 9 6 3 5 2 7 0。

左边为：8，右边为0，中间为6。

这里取三个数排序后，中间那个数作为枢轴，则枢轴为6。

插入排序：

当待排序序列的长度分割到一定大小后，使用插入排序。

原因：对于很小和部分有序的数组，快排不如插排好。

当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排。

重复数组：

在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割。

在一次划分后，把与key相等的元素聚在一起，能减少迭代次数，效率会提高不少。

在处理过程中，会有两个步骤：

  • 第一步，在划分过程中，把与key相等元素放入数组的两端。
  • 第二步，划分结束后，把与key相等的元素移到枢轴周围。