活动地址：21天学习挑战赛

 

文章目录

 一、算法

1.算法概述

2.算法步骤

3.算法特点

二、算法实践

1.Java代码

2.执行结果

3.讲解视频 

三、复杂度分析

1.时间复杂度

2.空间复杂度

---

 一、算法

1.算法概述

快速排序（Quick Sort）是由冒泡排序改进而成的。在冒泡排序中，每次只对相邻的两个记录进行比较，因此每一次交换相邻记录时只能一次消除一个逆序；而快速排序则是对这一缺点进行改进，它通过交换两个（不相邻）的记录来消除多个逆序，从而大大加快了排序的速度，提升了排序的性能。

文章传送门 ：经典算法之冒泡排序与直接选择排序

2.算法步骤

• 在待排序的n个记录中任取一个记录（通常取第一个元素）作为枢轴，设其关键字为key
• 经过一趟排序后，把所有关键字小于key的记录交换放到key前面，把所有关键字记录大于key的记录交换放到key后面，结果将待排序的记录分成了两个子表，最后将枢轴key放到分界处的位置
• 然后，分别对上面的左、右两个子表重复上述的过程，直至每一个子表只有一个元素时，则排序完成

其中一趟快速排序的具体步骤如下：

1. 选择待排序表中的第一个记录作为枢轴, 将枢轴记录暂存在r[0]的位置上。附设两个指针low和high,初始时分别指向表的下界和上界(第一趟时，low= 1; high = L.length; )。
2. 从表的最右侧位置依次向左搜索,找到第一个关键字小于枢轴关键字key的记录,将其移到low处。具体操作是：当low
3. 再从表的最左侧位置,依次向右搜索找到第-一个关键字大于key的记录和枢轴记
   录交换。具体操作是:当low 指针low (执行操作++low );否则将low所指记录与枢轴记录交换。
4. 复步骤2和3，直至low与high相等为止。此时low或high的位置即为枢轴在此趟排
   序中的最终位置，原表被分成两个子表。

在上述过程中，记录的交换都是与枢轴之间发生，每次交换都要移动3次记录，可以先将枢
轴记录暂存在r[0]的位置上，排序过程中只移动要与枢轴交换的记录，即只做r[low]或r[high]的
单向移动，直至一趟排序结束后再将枢轴记录移至正确位置上。
 

3.算法特点

• 由于记录是非顺次移动导致快速排序是不稳定排序
• 排序过程中需要定位表的下界和上界，所以适用于顺序结构，很少用于链式结构
• 当n较大时，在平均情况下快速排序是所有内部排序中速度最快的一种
• 故其适用于初始记录无序、n较大的情况

---

二、算法实践

1.Java代码

package TwentyOne_Challenge;
 
public class DayEight{
    public static void main(String[] args) {
        int a[]={7,13,6,50,25,78,11,100};
        System.out.println("原来无序序列为：");
        for (int i = 0; i < a.length ; i++) {
            System.out.print(a[i]+" ");
        }
        System.out.println();
        System.out.println("经快速排序后：");
        //快速排序法
        quickSort(a);
        for (int i = 0; i < a.length ; i++) {
            System.out.print(a[i]+" ");
        }
    }
    private static void quickSort(int[] array) {
        quickSortFunc(array, 0, array.length-1);
    }
    private static void quickSortFunc(int[] array, int start, int end) {
        if (start >= end) return;
        //找基准值的下标
        int keyIndex = findKey(array, start, end);
        //对左子序列进行递归快速排序
        quickSortFunc(array, start, keyIndex-1);
        //对右子序列进行递归快速排序
        quickSortFunc(array, keyIndex+1, end);
    }
    private static int findKey(int[] array, int left, int right) {
        //取左边界元素为基准值，该位置“挖坑”
        int key = array[left];
        int start = left;
        int end = right;
        while (start < end) {
            //从右往左扫描，寻找比key小的记录
            while (start < end && array[end] >= key) {
                end--;
            }
            array[start] = array[end];
            //从左往右扫描，寻找比key大的记录
            while (start < end && array[start] <= key) {
                start++;
            }
            array[end] = array[start];
        }
        //start与end相等时的位置，即到达基准值位置
        array[start] = key;
        //返回基准值的下标
        return start;
    }
}

2.执行结果

3.讲解视频 

 （注：视频来源于B站up主：codereasy） 

---

三、复杂度分析

注：以下图片来自于教材《数据结构(C语言版)》——严蔚敏 李冬梅 吴伟民 编著

1.时间复杂度

2.空间复杂度