前言

         什么是快速排序?  这是我之前遇到的一个面试题，当时没回答来，现在补一下快速排序。

1. 什么是快速排序算法？

        快速排序算法是对冒泡排序算法的一种改进，没有冒泡排序两两相邻之间的比较换位，主要采用的思想是通过递归+独立排序的形式将无序的数列进行分割成可以独立排序的2部分数列，其中一部分数列比另外一部书数列小，每次排序两个独立的数列，直到排序完毕，即可完成最终的排序。

        简单讲就是每次定义一个临界值，将大值放在临界值的右边，小值放到临界值的左边。

2. 快速排序的实现步骤

        1) 从左边定义一个i =0，右边定义一个j= arr.length-1 , 定义第一个分界值为 a[0], i++ ,直到找到第一个比a[i]大的值，然后a[i]与a[j] 互换位置。

        2)  从右边定义一个j,  j--, 找到比第一个比a[0]小的值a[j]与a[i]互换位置，这里为什么j--和i++ 是因为已经满足有序，不需要再进行交换了。

        3) 如果循环的i-1>start 或 j+1>end, 那么重复步骤1 ) 2) ,直到 i==j，循环结束, 排序完毕。

3. 代码实现

JAVA 版

package sort;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

import java.util.Arrays;

/**
 * 快速排序算法思想:
 * 1. 首先设置数组的第一个值为临界值，将数组的值按照此临界值分为2个部分。
 * 2. 将大于该临界值的值放入到临界值的右边，小于该临界值的值放入到临界值的右边。
 * 3. 然后将左边的序列再取一个分界值，将该部分数据分成左右2个部分，同样的小于临界值的放在左边，大于临界值的数放在右边。
 * 4.  重复上述过程，直到排序完毕。
 * 算法时间复杂度:
 */
public class QuickSort {


    public static void main(String[] args) {
        int[] a = new int[]{46,38,1,456,23,48,59,34,27,16,60};
        System.out.println("排序前:" + Arrays.toString(a));
        int[] result = quickSort(a, 0, a.length - 1);
        System.out.println("排序后:" + Arrays.toString(result));
    }


    // 快速排序
    public static int[] quickSort(int[] arr, int start, int end) {

        int criticalValue = arr[start];
        int i = start;
        int j = end;

        while (i < j) {

            // 如果左边的比临界值小，那么就i++
            while (i < j && arr[i] < criticalValue) {
                i++;
            }

            //如果右边的值比临界值大，那么就j--。
            while (i < j && arr[j] > criticalValue) {
                j--;
            }

            // 如果两值正好相等，那么就继续右移
            if (i < j && arr[i] == arr[j]) {
                i++;
            }
            //基于临界值两边，如果arr[i]>arr[j],那么就将大值放到右边去。
            if (arr[i] > arr[j]) {
                swap(i, j, arr);
            }
        }

        if (i - 1 > start) {
            arr = quickSort(arr, start, i - 1);
        }

        if (j + 1 < end) {
            arr = quickSort(arr, j + 1, end);
        }

        return arr;

    }


    public static void swap(int index1, int index2, int[] arr) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

打印结果:

排序前:[46, 38, 1, 456, 23, 48, 59, 34, 27, 16, 60]
排序后:[1, 16, 23, 27, 34, 38, 46, 48, 59, 60, 456]

快速排序的平均时间复杂度为o(nlog2n)， 单次排序即可挪动两边数据进行大小比较。

Python 版 

def quick_sort(arr):
  if len(arr)<=1:
      return arr
  pivot=arr[0]
  less=[x for x in arr[1:] if x<=pivot]
  greater=[x for x in arr[1:] if x>pivot]
  return quick_sort(less)+[pivot]+quick_sort(greater)


# Press the green button in the gutter to run the script.
if __name__ == '__main__':
    my_array=[5,9,1,7,6]
    sorted_array=quick_sort(my_array)
    print(sorted_array)

python 实现的思想是一样，找临界值，然后根据临界值找到2个数组，第一个数组为比临界值小的数组 left_array, 另外一个数组为比临界值大的数组，然后对left_array和right_array进行递归处理，打印结果:

[1, 5, 6, 7, 9]