1.排序分类

比较排序：冒泡排序、选择排序、插入排序、归并排序、堆排序、快速排序（时间复杂度O(nlogn)~O(n^2)）
非比较排序：计数、基数排序、桶排序（时间复杂度O（n））

image.png

2.冒泡排序

方法：

1.比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定

// 冒泡排序
int bubble(int *a, int length){
    int i=0,j=0;
    for (i;i<length-1;i++)
    {
        for (j;j<length-1-i;j++)
        {
            if (a[j]>a[j+1])
            {
                int temp = a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
    return 0;
}

3、鸡尾酒算法（定向冒泡排序）

方法：
区别于冒泡排序只是从低到高，鸡尾酒排序是先由底到高将最大数送到最后，再由高到低将最小数送到最前面，如此循环

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果序列在一开始已经大部分排序过的话,会接近O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定

// 鸡尾酒算法

int bubble_improve(int *a,int length){
    int left=0;
    int right=0;
    while (left<right)
    {
        for (int i=left;i<right;i++)
        {
            if (a[i]>a[i+1])
            {
                int temp=a[i];
                a[i]=a[i+1];
                a[i+1]=temp;
            }
        }
        right--;
        for (int i=right;i>left;i--)
        {
            if (a[i]<a[i-1])
            {
                int temp=a[i];
                a[i]=a[i-1];
                a[i-1]=temp;
            }
            
        }
        left--;
    }
    return 0;
}

** 注：循环一个从正向一个从反向，一个加一个减，两头都要考虑；两个全局变量的增减是相反的
在乱数序列的状态下，鸡尾酒排序与冒泡排序的效率都很差劲。**

4、选择排序

方法：

1.初始时在序列中找到最小元素，放到序列的起始位置作为已排序序列；
2.然后，再从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

    与冒泡排序的区别：
    冒泡排序是依次交换两个相邻顺序不合法的元素位置；
    选择排序是遍历一次记住最小的元素的位置，最后仅需交换一次就可以放到合适的位置。

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- O(n^2)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定
void swap(int a[],int i,int j){
    int temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}

int select(int* a, int length){
    int min = 0;
    for(int i=0; i<length - 1; i++){  //已排
        min =i;
        for(int j = i + 1; j<length; j++){ //未排
            if(a[j]<a[min]){
                min = j;
            }
        }
        if(a[i]!=min){
            swap(a, i,min);
        }
    }
    return 0;
}

** 注：已经排序的序列和尚未排序的序列要区分开，循环条件也要区别开。选择排序是不稳定的排序算法，不稳定发生在最小元素与A[i]交换的时刻。**

5、插入排序

方法：
对于未排序数据（右手抓到的牌），在已经排序序列（左手已经排好序的牌）中从后向前扫描，并找到相应的位置插入。
···

···

排序总结