排序-快速排序

一，基本信息

描述

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

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

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

案例

复杂度

• 时间复杂度
  • 平均最好O(NlogN)
  • 最坏 O(N2)
    • 每次划分分为一个元素，和 其他元素 两个部分。
• 空间复杂度: 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));
    }
}

二、 稳定性。

• 稳定性定义
  • 稳定排序算法会让原本有相等键值的纪录维持相对次序。

1. 用一个O(N) 内存来 实现快排的稳定性

• 寻找中间数的下标 只能是第一个。
  • 3 2 3 3 4。如果选 2 下标的3 ，还是会打乱顺序。

public class QuickPacifySort {

    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) {
        if( low >= high) {
            return low;
        }
        int offset = low;
        long middleValue = sqList[low];

        List<Long> leftList = new ArrayList<>();
        List<Long> rightList = new ArrayList<>();

        for(int i = low; i <= high; i ++) {
            if(sqList[i] < middleValue) {
                leftList.add(sqList[i]);
            } else {
                rightList.add(sqList[i]);
            }
        }
        int start = 0;
        for(; start < leftList.size(); start ++) {
            sqList[low + start] = leftList.get(start);
        }
        start = low + start;
        for(int i = 0; i < rightList.size(); i ++) {
            sqList[start ++] = rightList.get(i);
        }
        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};
        QuickPacifySort quickSort = new QuickPacifySort();
        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));
    }
}