2018-04-20 快速排序

作者: uin_sisyphus | 来源:发表于2018-10-30 15:14 被阅读0次

2018-04-20 快速排序
2018-04-20
七大排序算法之快速排序
面试准备--排序
排序
算法笔记01-排序#2
PHP 实现快速排序
快速排序的Python实现
数据结构与算法快速排序
数组-快速排序

快速排序使用较广，效率挺高。

数组中存在两个相等的数字时候------

主要思路是：取个值作为key（一般取数组第一个，这里不考虑各种优化），
从数组的头部和尾部开始和key比较，小的放在key的左侧，大的放在key的右侧（快速排序有个别名叫填坑法，能很好的说明具体的比较赋值的动作），
-------一趟下来之后key的位置就是最终的位置了，
此时将key的左侧和右侧继续按照上面的方法操作（递归）

时间复杂度
O(nlog 2 n)
空间复杂度
O(log2 n)

java 实现
两个函数的快速排序

    private static int partition(int a[], int i, int j) {
        int key = a[i];// key值
        while (i < j) {
            while (i < j && a[j] > key)
                // 从右向左小循环
                j--;
            if (a[j] <= key)// 判定填充
                a[i] = a[j];
            while (i < j && a[i] < key)
                // 从左向右小循环
                i++;
            if (a[i] >= key)// 判定填充
                a[j] = a[i];
        }
        a[i] = key;// 把轴元素放在轴所在地位置
        return i;// 返回轴所在的位置
    }

实现递归的quicksort():

    private void quickSort(int data[], int low, int high) {// 递归
        int q;
        if (low < high) {
            q = partition(data, low, high);
            quickSort(data, q + 1, high);// 对q左边进行分类
            quickSort(data, low, q - 1);// 对q右边进行分类
        }
    }

一个函数的快速排序

    public static void QuickSort(int[] R, int low, int high){
        int temp;
        int i = low, j= high;
        if(low < high){
            temp = R[low];
            while(i<j){
                while(j>i && R[j]>=temp) j--;
                if(i<j){
                    R[i]=R[j];
                    i++;
                }
                while(j>i && R[i]<=temp) i++;
                if(i<j){
                    R[j]= R[i];
                    j--;
                }
            }
            //一趟排序走完最终确定
            R[i] = temp;
            QuickSort(R,low,i-1);
            QuickSort(R,i+1, high);
        }
    }