常见排序算法

冒泡排序

每一次循环将最大的一个数换到最右边
最好情况，顺序T=O(n)
最坏情况，逆序T=O(n2)

平均时间复杂度，T=O(n2)

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

插入排序

每次选择一个数，依次和已排序好的数据对比，如果大直接插入，如果小交换
最好的情况，顺序 T=O(n)
最坏的情况，逆序 T=O(n2)
平均时间复杂度，T= O(n2)
插入排序是一种稳定的排序算法

void Insertion_Sort(int a[], int n) {
    for(int i = 1;i < n; i++) {
        int tmp = a[I];
        int j = I;
        for(;j>0 && tmp < a[j - 1];j--) {
            a[j] = a[j - 1];
        }
        a[j] = tmp;
    }
}

希尔排序

希尔排序是简单插入排序的改进版。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序
最坏的情况下 T= O(n2)

void Shell_Sort(int a[], int n) {
    for(int gap = n / 2; gap > 0; gap = gap / 2) {
        for(int i = gap;i < n ; i++) {
            int tmp = a[I];
            int j = I;
            for(; j >= gap && tmp < a[j - gap]; j -= gap) {
                a[j] = a[j - gap];
            }
            a[j] = tmp;
        }
    }
}

选择排序

每次循环获取到当前最大的索引，执行交换
时间复杂度：T=O(n2)
稳定

void Selection_Sort(int a[], int n) {
    for(int i = 0; i < n; i++) {
        int k = I;
        for(j = k + 1; j < n; j++) {
            if(a[j] > a[k]) {
                k = j;
            }
        }
        
        int tmp = a[k];
        a[k] = a[I];
        a[i] = tmp;
    }
}

堆排序

将待排序的序列构建成大顶堆，每次将堆顶元素和最后一个元素做交换，再循环堆化二叉树，将堆顶的最大值和最后一个元素做交换，最后得到的就是排序好的数据

时间复杂度： O(nlogn)

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

• 把长度为n的输入序列分成两个长度为n/2的子序列
• 对这两个子序列采用归并排序
• 将两个排序好的子序列合并成一个最终的排序序列

时间复杂度：T= O(nlogn)

快速排序

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

• 从序列中挑选一个主元（pivot）
• 将序列根据主元分成2个独立子集
• 对子集继续地柜调用快速排序

时间复杂度：T = O(nlogn)

基数排序

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

• 取得数组中的最大数，并取得位数
• arr为原始数组，从最低位开始取每个位组成radix数组
• 对radix进行计数排序

时间复杂度：T= O(P(N+B))

桶排序

假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序

• 设置一个定量的数组当做空桶
• 遍历输入数组，并且把数据一个一个放到对应的桶中
• 对每个不是空的桶进行排序
• 从不是空的桶中把排好序的数据拼接起来

时间复杂度：T= O(N+M) M是桶的数目

排序算法的比较

16335126184472.jpg