【数据结构初阶】八大排序(二)——快速排序&&冒泡排序

大家好���是沐曦希

书接【数据结构初阶】八大排序(一)——希尔排序&&堆排序&&直接插入排序&&直接选择排序

文章目录

• 1.交换排序
• • 1.1 冒泡排序
  • • 排序性能对比
    • 1.2 快速排序
    • • 1.2.1 hoare版本
      • • 具体思路
        • 代码
        • 1.2.2 挖坑法
        • • 具体思路
          • 代码
          • 1.2.3 前后指针版本
          • • 具体思路
            • 代码
            • 1.3 快速排序的优化
            • • • 1.3.1 三数取中法选基准值
                • 1.3.2 小区间优化
                • 1.3.3 完整代码
                • 排序性能对比
                • 1.4 快速排序非递归
                • • 1.4.1 具体思路
                  • 代码
                  • 1.5 快速排序的特性总结
                  • 2.写在最后

                    ---

                    1.交换排序

                    基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

                    1.1 冒泡排序

                    void BubbleSort(int* a, int n){int flag = 1;int i = 0;for (i = 0; i  a[j + 1]){Swap(&a[j], &a[j + 1]);flag = 0;}}if (flag == 1)break;}}int main(){int a[] = { 11,45,33,18,36,41,39,35,21,31,17,10,28 };BubbleSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));return 0;}

                    冒泡排序的特性总结：

                    1. 冒泡排序是一种非常容易理解的排序
                    2. 时间复杂度：O(N^2)
                    3. 空间复杂度：O(1)
                    4. 稳定性：稳定

                    排序性能对比

                    void testOp(){srand((unsigned int)time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);assert(a1);int* a2 = (int*)malloc(sizeof(int) * N);assert(a2);int* a3 = (int*)malloc(sizeof(int) * N);assert(a3);int* a4 = (int*)malloc(sizeof(int) * N);assert(a4);int* a5 = (int*)malloc(sizeof(int) * N);assert(a5);for (int i = 0; i  
                    当N为10000时.
                     
                    1.2 快速排序
                       
                    快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
                      
                    // 假设按照升序对array数组中[left, right)区间中的元素进行排序void QuickSort(int array[], int left, int right){if(right - left int keyi = left;int begin = left;int end = right;while (left  left){--right;}//left找大while (a[left]  left){++left;}if(left   
                    1.2.2 挖坑法
                     
                    挖坑法与上面的方法类似。
                     
                    具体思路
                     
                    先将选定的基准值(最左边)直接取出，然后留下一个坑。
                    当右指针遇到小于基准值的数时，直接将该值放入坑中，而右指针指向的位置形成新的坑位，
                    然后左指针遇到大于基准值的数时，将该值放入坑中，左指针指向的位置形成坑位，
                    重复该步骤，直到左右指针相等。最后将基准值放入坑位之中。
                    之后也是以基准值为界限，递归排序基准值左右区间。
                         
                    单趟演示：
                     
                    重复以上步骤直到左右指针相遇：
                    此时就把序列分为6之前的左序列和右序列，再用递归分别对左序列和右序列进行排序，每次排好一个数字位置。
                     
                    代码
                     
                    //挖坑法int PartSort2(int* a, int left, int right){int key = a[left];int hole = left;while (left = key)--right;a[hole] = a[right];hole = right;//左边找大，填到右边的坑while (left  a[right])return left;elsereturn right;}else//a[mid] if (a[mid]  a[right])return mid;else if (a[left] = right)return;if (right - left InsertSort(a + left, right - left + 1);}else{//单躺排序//int keyi = PartSort1(a, left, right);int keyi = PartSort2(a, left, right);//int keyi = PartSort3(a, left, right);//[left,keyi-1] keyi [keyi+1,right]QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}}//挖坑法int PartSort2(int* a, int left, int right){//三数取中int mid = getmidindex(a, left, right);Swap(&a[left], &a[mid]);int key = a[left];int hole = left;while (left