排序算法

# 排序算法

# 概述

算法分类：

十种常见排序算法主要分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O (nlogn)，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。


算法复杂度


# 交换排序

# 1. 冒泡排序

1.1 算法描述

选定一个元素依次和后面的元素进行比较大小，如果大于 (小于) 那么就交换两个数的位置

例如：[2,5,1,4,6,8] 从小到大排序

1. 2 比 5 小，满足条件，不用交换
2. 5 比 1 大，所以交换顺序变成 [2,1,5,4,6,8]
3. 5 比 4 大，所以变成 [2,1,4,5,6,8]

..........

直到全部比较完即可得到最终的排序结果

1.2 代码实现

#include <cstdio>
//冒泡排序
void BubleSort(int ans[],int len){
    for(int i=0;i<len;i++){
        for(int j=0;j<len-1-i;j++){
            if(ans[j]>ans[j+1]){
                int q=ans[j+1];
                ans[j+1] = ans[j];
                ans[j] = q;
            }
        }
    }
}
int main(){
    int un[]={3,2,5,1,5,2};
    BubleSort(un,6);
    for(int i=0;i<6;i++){
        printf("%d",un[i]);
    }

    return 0;
}

# 2. 选择排序

2.1 算法描述

选择排序首先在一个未排序的数组 n 里面找到一个最大 (最小) 元素，然后与第一个元素进行交换位置，再接着寻找从 n 里面寻找第二大数值与第二个元素交换顺序，一直循环往后，直到倒数第二个元素和最后一个元素交换顺序。

2.2 代码实现

// C++ source file
#include <stdio.h>

void selectionSort(int ans[]){
    int l=sizeof(ans)-1;
    for(int i=0; i<l; i++) {
        for(int j=i; j<l; j++) {
            if(ans[i]<ans[j]){
                int tmp=ans[i];
                ans[i]=ans[j];
                ans[j]=tmp;
            }
        }
    }
}
int main(){
    int ans[]={1,2,3,4,5,6,7};
    selectionSort(ans);
    int l=sizeof(ans)/sizeof(int);
    for(int i=0; i<l; i++) {
        printf("%d", ans[i]);
    }

    return 0;
}

# 3. 插入排序

3.1 算法描述

将未排序数组分为两部分，从第一个元素开始，进行排序，前面为已经排序好数组，以此向后扫描，对已经排序好的部分进行比较小大并插入

3.2 代码实现

// C++ source file
#include <stdio.h>

void insert_sort(int ans[]){
    int l=sizeof(ans)-1;
    for(int i=1; i<l; i++) {
        int key=ans[i];
        int j=i-1;
        while(j>=0&&key<ans[j]) {
            ans[j+1]=ans[j];
            j--;
        }
        ans[j+1]=key;
    }
}
int main(){
    int ans[]={2,5,2,6,3,1,4};
    insert_sort(ans);
    int l=sizeof(ans)/sizeof(int);
    for(int i=0; i<l; i++) {
        printf("%d", ans[i]);
    }

    return 0;
}

# 4. 希尔排序

算法描述：

希尔排序是对插入排序的一种更高效的排序方法

它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

适用说明

希尔排序时间复杂度是 O(n^(1.3-2))，空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n^2 ) 复杂度的算法快得多。

template<typename T>
void shell_sort(T array[], int length) {
    int h = 1;
    while (h < length / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
                std::swap(array[j], array[j - h]);
            }
        }
        h = h / 3;
    }
}