实验二 典型排序算法训练：快速排序、计数排序

一、快速排序

1. 算法原理

​ 快速排序的思想是任找一个元素作为基准，对待排数组进行分组，使基准元

素左边的数据比基准数据要小，右边的数据比基准数据要大，这样基准元素就放

在了正确的位置上。然后对基准元素左边和右边的组进行相同的操作，最后将数

据排序完成。

2. 流程图

3. 正确性分析

​ 1）初始：i=p-1，j=p，p 与 i 之间、i+1 与 j-1 之间为空，正确性成立。

​ 2）保持：循环开始前，a[p]至 a[i]的值小于 x，a[i+1]至 a[j-1]的值大于 x。进 入循环后，如果 a[j]<x，i++，交换 a[i]与 a[j]，否则不变，只进行保证了 a[i]前的 值小于 x，a[i+1]至 a[j]的值大于 x，保证正确性，进入下一循环。

​ 3）结束：j=r，循环结束，此时 a[p]至 a[i]的数小于 x，a[i+1]至 a[r-1]的数大 于 x，交换 a[i+1]与 a[r]，此时 a[p]至 a[i]的数小于 a[i+1]， a[i+2]至 a[r]的数大于 a[i+1]，返回值 i+1 标识了参照值的下标位置。

4. 实现代码

public class public class QuickSort {
    public static void quickSort(int a[],int p,int r){
        if (p < r){
            int q = partition(a,p,r);
            quickSort(a,p,q-1);
            quickSort(a,q +1 ,r);
        }
    }

    private static int partition(int[] a, int p, int r) {
        int x = a[r];
        int i = p - 1;
        for (int j = p; j <= r - 1; j++) {
            if (a[j] <= x){
               i++;
                swap(a, i, j);
            }
        }
        swap(a,i+1,r);
        return i + 1;
    }
	  private static void swap(int[] a, int i, int j) {
        int temp = a[j];
        a[j] = a[i];
        a[i] = temp;
    }

    public static void main(String[] args) {
        int[] a = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        QuickSort.quickSort(a,0,a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}

5. 实验结果

6. 时空和空间性能

时间复杂度：平均情况下O(nlgn)，在待排数组初始基本有序时，达到最坏情况O(n^2^)

空间复杂度: O(lgn)

二、计数排序

1. 算法原理

​ 计数排序的基本思想是：对每一个输入元素x，确定小于x的元素个数。利用这一信息，就可以直接把x放到它在输出数组中的位置上了。例如，如果有17个元素小于x，则x就应该在第18个输出位置上

2. 流程图

3. 正确性分析

​ 1）初始：结果数组为空，正确性成立。

​ 2）保持：c 中包含小于或等于 i 的元素个数，每输出一个 a 中元素至 b，c 中对应位置元素减一，按位置输出，循环不变式成立；

​ 3）结束：c 中元素归 0，b 按大小顺序输出元素，成立。

4. 实现代码

public class public class CountingSort {

    public static void countingSort(int[] a,int[] b,int k){
        int[] c = new int[k+1];
        for (int i = 0; i <= k ; i++) {
            c[i] = 0;
        }
        for (int i = 0; i < a.length; i++) {
            c[a[i]] = c[a[i]] + 1;
        }
        //now c[i]表示原始数组中数i的个数
        for (int i = 1; i <= k ; i++) {
            c[i] = c[i] + c[i - 1];
        }
        //now c[i]表示<=i的个数
        for (int i = a.length - 1; i >= 0 ; i--) {
            int t = a[i];
            b[c[t] - 1] = t; //a[j]的最终位置
            c[t] = c[t] - 1;
        }
    }

    public static void main(String[] args) {
        int[] a = new int[]{95,94,91,98,99,90,99,93,91,92};
        int[] b = new int[a.length];
        int k = 99;
        countingSort(a,b,k);
        System.out.println(Arrays.toString(b));
    }
}

5. 实验结果

6. 时空和空间性能

时间复杂度：O(n + k),k为原数组大小，k为辅助数组大小

空间复杂度：两个辅助数组O(n + k)

三、两种算法的区别

区别：

1. 快排是不稳定的，计数排序是稳定的
2. 快排是基于比较的，计数排序不是
3. 时间复杂度不同
4. 快排是在原数组上排序，计数排序是要辅助数组的