快速排序 | 晨星的博客

一个比较经典的的排序算法

快速排序的由来

快速排序（英语：Quicksort），又称分区交换排序（英语：partition-exchange sort），简称「快排」

英国计算机科学家Tony Hoare在1960年为了解决计算机上的排序问题，提出了快速排序的算法，最初是为了在英国的英尔兰电子公司（ELLIOTT Brothers）的快速硬件上实现高效的排序算法。[1]

基本原理

快速排序的工作原理是通过递归中的分治思想的方式来将一个数组排序。

从待排序的数组中选择一个元素，称之为枢纽元（pivot）。
将数组中小于枢纽元的元素移到枢纽元的左边，将大于枢纽元的元素移到枢纽元的右边，这个过程称为分区（partition）。
递归地对枢纽元左边的子数组和右边的子数组进行排序。
当所有子数组都有序时，整个数组就自然有序了。

代码实现

整个流程最重要的就是partition过程了：

从待排序的数组中选择一个元素当作基准；

左右分别设置一个指针（也就是小于和大于那个基准的范围）；

再建立一个当前指针进行遍历：

当大于基准时：当前位置与左边界的前一个交换，左边界右移加一，当前指针++；

当小于基准时：当前位置与右边界的前一个交换，右边界左移减一，当前指针++；

当等于基准时：当前指针++；

接着对两边的数组在进行partition过程，相当于进行递归调用

代码如下

	public static int[] partition(int[] arr, int num) {
        int left = -1;
        int right = arr.length;
        for (int i = 0; i < right; ) {
            if (arr[i] > num) {
                swap(arr, i, right - 1);
                right--;
            }
            if (arr[i] < num) {
                swap(arr, i, left + 1);
                i++;
                left++;
            }
            if (arr[i] == num) i++;
        }
        //返回左右边界 下次递归需要使用
        return new int[]{left + 1, right};
    }
//数组元素交换
    public static void swap(int[] arr, int i, int j) {
        if (i == j) return;
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

随即快排（优化）

但是num的选择有一点讲究，

如果我们每次都选固定的位置会造成：数据情况会对时间复杂度造成影响

比如 1，2，3，4，5，6，7，8，9 这样的数据

那每次我们都选最后一个做基准就会发现每次只能排好最后一个数

时间复杂度将退化为N平方

所以我们引入一个随机快排的概念，即随机选一个数做基准，经过概率计算得出期望时间复杂度的函数为

$N*log(N)$

代码如下：

   
  public static void quickSort(int[] arr, int l, int r) {
       if (arr == null || arr.length == 0 || arr.length == 1) return;
       if (l >= r) return;
       int[] partition = partition(arr, l, r);
      	//对两边的数组在进行partition过程，递归调用
       quickSort(arr, l, partition[0] - 1);
       quickSort(arr, partition[1] + 1, r);

   }


public static int[] partition(int[] arr, int l, int r) {
       if (l > r) return new int[]{-1, -1};
       if (l == r) return new int[]{l, r};
       int left = l - 1;
       int right = r;
       Random random = new Random();
       //随机选值
       int randomNum = random.nextInt(r - l + 1) + l;
       //放到最后 避免影响排序
       swap(arr, randomNum, r);
       for (int i = l; i < right; ) {
           if (arr[i] > arr[r]) swap(arr, i, --right);
           if (arr[i] < arr[r]) swap(arr, i++, ++left);
           if (arr[i] == arr[r]) i++;
       }
       //选的值进行插入
       swap(arr, right, r);
       //返回左右边界 下次递归需要使用
       return new int[]{left + 1, right};
   }

//数组元素交换
   public static void swap(int[] arr, int i, int j) {
       if (i == j) return;
       arr[i] = arr[i] ^ arr[j];
       arr[j] = arr[i] ^ arr[j];
       arr[i] = arr[i] ^ arr[j];
   }

当然实际排序时可以根据数据情况来进行选择使用排序方式

如短数据采用插入排序等；

总结

时间复杂度的函数为

$O(N*log(N))$

空间复杂度即递归栈的空间复杂度

$O(log(N))$

由于随机选择的特性不能保证原先的顺序所以是一个不稳定的排序算法

每日一句

多数人在25岁时就死了，一直到75岁才埋葬 —— 富兰克林 [2]

参考

Wiki百科