排序算法之交换类排序

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/FrankieHello/article/details/83186578

交换类排序

交换类排序的思想，顾名思义，就是在每一轮的排序过程，通过不断的交换来使每个元素到达最终的位置。常见的两种交换类排序有冒泡排序和快速排序。

冒泡排序（Bubble sort）

冒泡排序作为最基础的排序算法，它的排序思想也如其名，通过比较两个相邻数据的大小，来决定是否交换它们的位置，最后经过多轮排序最终是整个序列有序。

网上找到的gif动图：

代码：

void sortBubble(int a[], int n){
    int i=0, j=0;
    int temp;
    for(i=0; i<n; i++){
        for(j=i+1;j<n;j++){
            if (a[i]>a[j]){
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
}


int main()
{
    int a[] = {1,2,3,2,5,6};
    int i = 0;
    sortPao(a, 6);
    for(i = 0; i<6;i++){
        printf("%d ",a[i]);
    }
    return 0;
}

分析：

从代码中可以看出最内层的交换操作可以看做是基本操作。

时间复杂度：当内层if语句始终成立时，也就是序列正好是逆序时，需要执行n(n-1)/2次，所以时间复杂度是。

                      当内层if语句不执行时，也就是序列是是有序的时候，也就是需要遍历一次，时间复杂度是。

                      所以综合上，平均时间复杂度就是。

空间复杂度：从代码中就可以看出，整个排序过程只需要一个temp变量来辅助，所以空间复杂度是。

快速排序(Quick sort)

快速排序也是一种交换类的排序算法，它的思想就是每一轮先选择当前序列中的一个关键字（通常是序列中的第一个）作为枢纽，然后从序列中从前往后找到一个比它大（小）的数据，再从后往前找到一个比它小（大）的数据，然后交换它们的位置，直到它们相遇，相遇的位置即是枢纽的位置，同时也将枢纽左边都是比它小（大）的，右边都是比它大（小）的，然后再通过递归来对子序列进行排序。

gif动图：

代码：

void sortQuick(int a[], int low, int high) {
    int i, j;
    int pivot, temp;
    center = a[low];
    if(low < high) {
        i = low;
        j = high;
        while(i < j) {
            while(j > i && a[j] >= pivot) {   //from right to left to find one bigger than pivot
                j--;
            }
            while(i < j && a[i] <= pivot) {   //from left to right to find one smaller than pivot
                i++;
            }
            if(i<j) {                        //change position
                temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }else{
                a[low] = a[i];
                a[i] = pivot;
            }
        }
        sortQuick(a, i+1, high);              //recur the process
        sortQuick(a, low, i-1);
    }
}

int main() {
    int a[] = {1,2,3,2,5,6};
    int i = 0;
    sortQuick(a, 0, 5);
    for(i = 0; i<6; i++) {
        printf("%d ",a[i]);
    }
    return 0;
}

分析：

时间复杂度：快速排序最好情况（每次划分都是均匀划分）的时间复杂度是。

                      最坏的情况（待排序的序列是正序或者逆序时），复杂度是。

                      平均时间复杂度就是。

                       对时间复杂度的具体分析以后填。

空间复杂度：从代码中可以看出，快排是通过递归实现的，需要栈的辅助，空间复杂度是。

另外，快排的排序数和初始序列有关，序列越无序，效率越高；越接近无序，效率越低。

 

ref:《2019数据结构高分笔记》（天勤版本）