排序-快速排序

描述

• 被列为20世纪十大算法之一

• c++ STL, java SDK 等开放工具包的源代码都有它的某种实现版本

• 思路： 通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

案例

复杂度

• 时间复杂度：O(nlogn)
  • log 描述以 2为底对数
• 空间复杂度: O(logn)

代码

package com.datastructure.sort;

import java.util.Arrays;

/**
 * QuickSort class
 */
public class QuickSort {

    public void sort(long[] sqList, int low, int high){
        //中间数下标
        int middle;
        if(low < high) {
            //算出中间值下标
            middle = partition(sqList,low,high);
            sort(sqList,low,middle-1);
            sort(sqList,middle+1,high);
        }
    }

    public int partition(long[] sqList, int low, int high) {
        long t, middleValue = sqList[low];

        // 从数组两端交替向中间扫描
        while (low < high) {
            // 保证右边的大于等于中间值
            while (low < high && sqList[high] >= middleValue )
                high --;
            swap(sqList,low,high);
            // 保证左边的小于等于中间值
            while (low < high && sqList[low] <= middleValue)
                low ++;

            swap(sqList,low,high);

        }
        return low;
    }

    public void swap(long[] sqList, int low, int high) {
        long t = sqList[low];
        sqList[low] = sqList[high];
        sqList[high] = t;
    }

    public static void main(String[] args) {
        long[] sqList = {50,10,90,30,70,40,80,60,20};
        QuickSort quickSort = new QuickSort();
        quickSort.sort(sqList,0,sqList.length-1);
        System.out.println(Arrays.toString(sqList));

         sqList = new long[]{50, 10, 90, 30, 70, 40, 80, 60};
        quickSort.sort(sqList,0,sqList.length-1);
        System.out.println(Arrays.toString(sqList));
    }
}

• 控制台输出

[10, 20, 30, 40, 50, 60, 70, 80, 90]
[10, 30, 40, 50, 60, 70, 80, 90]

优化

• 优化选取中间数
  • 三数取中法
    • partition方法 middleValue = 中间(sqList[low],sqList[high], sqList[low + (hight- low) /2] )
• 优化不需要的交换
• 根据数据规模改变算法
• 并行处理
• 优化递归操作

代码

// 优化选取中间数 优化不需要的交换 后
package com.datastructure.sort;

import java.util.Arrays;

/**
 * QuickSort class
 */
public class QuickSort {

    public void sort(long[] sqList, int low, int high){
        //中间数下标
        int middle;
        if(low < high) {
            //算出中间值下标
            middle = partition(sqList,low,high);
            sort(sqList,low,middle-1);
            sort(sqList,middle+1,high);
        }
    }

    public int partition(long[] sqList, int low, int high) {
        long t;
        int m = low + (high - low) / 2 ;

        // 三个数 取中间值，把中间值放到sqList[low]
        if(sqList[low] > sqList[high])
            swap(sqList,low,high);
        if(sqList[m] > sqList[high])
            swap(sqList,m,high);
        if(sqList[m] > sqList[low] )
            swap(sqList,m,low);

        long middleValue = sqList[low];
        // 从数组两端交替向中间扫描
        while (low < high) {
            // 保证右边的大于等于中间值
            while (low < high && sqList[high] >= middleValue )
                high --;
            sqList[low] = sqList[high];
//            swap(sqList,low,high);

            // 保证左边的小于等于中间值
            while (low < high && sqList[low] <= middleValue)
                low ++;

            sqList[high] = sqList[low];
//            swap(sqList,low,high);

        }
        sqList[low] = middleValue;
        return low;
    }

    public void swap(long[] sqList, int low, int high) {
        long t = sqList[low];
        sqList[low] = sqList[high];
        sqList[high] = t;
    }

    public static void main(String[] args) {
        long[] sqList = {50,10,90,30,70,40,80,60,20};
        QuickSort quickSort = new QuickSort();
        quickSort.sort(sqList,0,sqList.length-1);
        System.out.println(Arrays.toString(sqList));

         sqList = new long[]{50, 10, 90, 30, 70, 40, 80, 60};
        quickSort.sort(sqList,0,sqList.length-1);
        System.out.println(Arrays.toString(sqList));
    }
}