简单通俗易懂学算法——十大常用排序算法(快速排序)

快速排序:是对冒泡排序的一种改进。

先说下快排的一个基本思想

使用分治法(Divide and conquer)策略来把一个序列(list)分为较小和较大的2个子序列,然后递归地排序两个子序列。

就是通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

大喊一声,nb! 

一个图:看懂很容易,想出来是真不简单 

简单通俗易懂学算法——十大常用排序算法(快速排序)

时间复杂度: 

最坏时间复杂度 简单通俗易懂学算法——十大常用排序算法(快速排序)
最优时间复杂度 简单通俗易懂学算法——十大常用排序算法(快速排序)
平均时间复杂度 简单通俗易懂学算法——十大常用排序算法(快速排序)

 

一个百科!!!

代码实现:

/**
 * 快速排序算法
 * 
 * @param arr
 *            待排序的数组
 * @param low
 *            排序数组的起始位置
 * @param hight
 *            排序的结束位置
 */

public static void quickSort_v1(int arr[], int low, int hight) {
    if (low < hight) {
        // 算出枢轴值
        int pivot = partition_v1(arr, low, hight);

        // 对小的数组进行递归排序
        quickSort_v1(arr, low, pivot - 1);
        // 对大的数组进行递归排序
        quickSort_v1(arr, pivot + 1, hight);
    }
}
/**
 * 快速排序的关键算法
 * 
 * @param arr
 *            排序的数组
 * @param low
 *            低位的下标
 * @param hight
 *            高位的下标
 * @return 枢轴的下标索引
 */
public static int partition_v1(int arr[], int low, int hight) {
    // 枢轴(就是一个基数而以)
    int pivotkey = arr[low];

    while (low < hight) {
        // 找到不比枢轴元素大的元素位置
        while (low < hight && arr[hight] >= pivotkey) {
            hight--;
        }
        // 交换元素位置,使得比枢轴大的元素位置都在右边
        swap(arr, low, hight);
        // 找到不比枢轴元素小的元素位置
        while (low < hight && arr[low] <= pivotkey) {
            low++;
        }
        // 交换元素位置,使得比枢轴小的元素位置都在左边
        swap(arr, low, hight);
    }
    // 返回枢轴元素的下标位置。
    return low;
}

// 简单的数组元素位置交换
private static void swap(int[] arr, int low, int hight) {
    int t = arr[low];
    arr[low] = arr[hight];
    arr[hight] = t;
}

对上面代码进行优化: 

public static void quickSort_v2(int arr[], int low, int hight) {
    if (hight > low) {
        while(low < hight) {
            // 算出枢轴值
            int pivot = partition_v2(arr, low, hight);
            
            /*
             * 如果待排序的序列划分的极端不平衡,递归的深度将趋近于n。
             * 递归会耗费一定的栈空间,参数越多,耗费的空间也就越多。
             * 通过减少递归,缩减堆栈的深度的,来提升整体性能。
             */
            
            // 对小的数组进行递归排序
            quickSort_v3(arr, low, pivot - 1);
            // 尾递归
            low = pivot + 1;
        }
    }
}

/**
 * partition_v1()的改进,优化枢轴选取和减少不必要的交换
 * @param arr 待排序的数组
 * @param low 低位是下标索引
 * @param hight 高位的下标索引
 * @return 枢轴的下标位置
 */
private static void quickSortV2(int[] arr, int low, int hight) {

    if ((hight - low + 1) > MAX_ARRAY_LENGTH) {

        if (hight > low) {
            while(low < hight) {
                // 算出枢轴值
                int pivot = partitionV3(arr, low, hight);
                
                /*
                 * 如果待排序的序列划分的极端不平衡,递归的深度将趋近于n。
                 * 递归会耗费一定的栈空间,参数越多,耗费的空间也就越多。
                 * 通过减少递归,缩减堆栈的深度的,来提升整体性能。
                 */
                
                // 对小的数组进行递归排序
                quickSortV2(arr, low, pivot - 1);
                // 尾递归
                low = pivot + 1;
            }
        } else {
            // 当数组(元素个数)很小的时候,快速排序反而不如插入排序了。
            binInsertSort(arr, low, hight);
        }
    }
}

 

上一篇:Directory traversal 目录遍历漏洞


下一篇:快速排序(java实现)