1.选择排序

1.双指针循环 i动一次，j遍历剩余数组
2.a[i] < a[j] 就交换
3.每一次循环完 a[i]就是最小值，i指针的右边永远都比a[i]大
4.不稳定性 例如:(7) 2 5 9 3 4 [7] 1 当我们利用选择排序算法进行排序时候,(7)和1调换,(7)就跑到了[7]的后面了,原来的次序改变了,这样就不稳定了.
5.选择排序是时间复杂度表现最稳定的排序算法之一，无论什么数据进去都是O(n²) 的时间复杂度…..所以用到它的时候，数据规模越小越好。这也是一般人想到最多的简单算法，简单粗暴。

//arr[]为待排序数组，n为数组长度
void selectSort(int arr[], int n)
{
    for(int i = 0; i < n; i++)
    {
        for(int j = i+1; j< n; j++)
        {
            if(arr[j] < arr[i])
            {
                int temp = arr[i];
                arr[i] = arr[j]
                arr[j] = temp;
            }
        }
    }
}

2.冒泡排序

1.冒泡排序是通过比较两个相邻元素的大小实现排序，如果前一个元素大于后一个元素，就交换这两个元素。这样就会让每一趟冒泡都能找到最大一个元素并放到最后
2.稳定性：它是指对同样的数据进行排序，会不会改变它的相对位置。比如 [ 1, 3, 2, 4, 2 ] 经过排序后，两个相同的元素 2 位置会不会被交换。冒泡排序是比较相邻两个元素的大小，显然不会破坏稳定性。
3.空间复杂度：由于整个排序过程是在原数据上进行操作，故为 O(1);
4.时间复杂度：由于嵌套了 2 层循环，最坏与平均都为 O(n^2); 最好是 O(n)

//array[]为待排序数组，n为数组长度
void bubbleSort(int arr[], int n)
{
    for(int i = 0; i < n - 1; i++)
    {
        for(int j = 0; j< n - 1 -i; j++)
        {
            if(arr[j] > arr[j+1])
            {
                int temp = arr[j+1];
                arr[j+1] = arr[j]
                arr[j] = temp;
            }
        }
    }
}

3.插入排序

1.分区域处理，把数组分为已排序区域和未排序区域，初始化的时候所有的数据都处在未排序区域中，已排序区域是空
2.依次从未排序区域中拿出一个数，插入到已排序区域中，这个时候要遍历已排序区域中的数字挨个做比较
3.i代表插入的位置，j是从i左边开始依次和要插入的数比大小。如果 a[j] > value, 那么 j 就要往左移一格，直到 a[j] < value, 然后把value插入到 a[j+1]的位置
4.从代码里我们可以看出，如果找到了合适的位置，就不会再进行比较了，就好比牌堆里抽出的一张牌本身就比我手里的牌都小，那么我只需要直接放在末尾就行了，不用一个一个去移动数据腾出位置插入到中间。
5.最坏与平均都为 O(n^2); 最好是 O(n)

//array[]为待排序数组，n为数组长度
void isSort(int arr[], int n) {
    for (int i = 1; i < n; i++) //默认看作第一个元素为有序，从第二个元素开始往前比较(因为相邻的比较所以是稳定的)
    {
        int value = arr[i]; //插入的值
        int j = i-1; // 这里必须在第二个 for loop外初始化j，否则最后无法获取j来插入数据
        for (j; j >= 0; j--) { // int j = i-1; 有序序列最后一个下标
            if (arr[j] > value) {
                arr[j+1] = arr[j];//移动数据
            } else {
                break;
            }
        }
        arr[j+1] = value; //插入数据, j=0在for loop外是为了能够在这里使用，否则 j只会存在于loop里
    }
}

4.希尔排序

#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;

int a[N];

void shell_sort(int a[], int size)
{
    int gap, i, j;
    int tmp;

    for(gap = size / 2; gap > 0; gap = gap / 2)
    {
        for(i = gap; i < size; i++)
        {
            tmp = a[i];

            for(j = i - gap; i >= 0 && a[j] > tmp; j = j - gap)
            {
                a[j + gap] = a[j];
            }

            a[j + gap] = tmp;
        }

    }
}

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);

    shell_sort(a, n);

    for(int i = 0; i < n; i++) cout << a[i] << " ";

    return 0;

}

桶排序

假如对数组nums进行桶排序，nums的长度为L，最小元素为A，最大元素为B。
则gap为(B-A)/L+1，桶的个数为(B-A)/gap+1。
另外一个重要的性质是，同一个桶中的元素相差最多为gap-1。
对nums中的元素nums[i]，确定放入哪个桶的公式为：(nums[i]-A)/gap

测试数据集

int main() {
    int d[] = { 12, 15, 9, 20, 6, 31, 24 };
    cout << "输入数组  { 12, 15, 9, 20, 6, 31, 24 } " << endl;
    InsertSort(d,7);
    cout << "排序后结果：";
    for (int i = 0; i < 7; i++)
    {
        cout << d[i]<<" ";
    }
}