初级排序算法

• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序

冒泡排序

思想:

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

效率:

比较:N - 1 + N - 2 + ...+ 3 + 2 + 1 ~O(N²/2)
交换:最少 0次 最多比较一次交换一次

即:N - 1 + N - 2 + ...+ 3 + 2 + 1 ~O(N²/2)

说明:

冒泡排序手绘

Code

    int a[10] = {4, 2, 5, 7, 8, 9, 10, 1, 6, 3};
    
    for (int i = 0; i < 10 - 1; i++) {
        
        for (int j = 0; j < 10 - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                exchange(&a[j], &a[j + 1]);
            }
        }
        
    }

选择排序

思想:

1. 找出数组中最小的那个元素，与数组中的第一个元素交换(如果第一个元素就是最小的元素那么它就和自己交换)。
2. 找出剩下元素中最小的元素，与数组中的第一个元素交换。如此往复， 直到将整个数组排序。

效率:对于长度为N的数组,选择排序需要大约N²/2次比较和N次交换

说明:

• 对于思想的第1步,找出数组中最小的那个元素需要次数:
  2 1 3 4 5五个数找出最小, 假设第一个最小,后边依次比较如果更小就交换,所以5个数字找出最小的那个数需要4次比较。

所以比较次数:

N-1 + N-2 + ...+ 3 + 2 + 1 = na₁ + n(n-1)d/2 = N(N-1)/2

选择排序

Code

     int a[] = {2, 8, 7, 1, 3, 5, 6, 4};
    
    for (int i = 0; i < N; i++) {
        int index = i;
        
        for (int j = i + 1; j < N; j++) {
            
            if (a[j] < a[index]) {
                index = j;
            }
            exchange(&a[index], &a[i]);
        }
        
    }

插入排序

思想:

1. 比如把4 插入 1 2 5 6 中
2. 4 < 6 前继续找合适位置插入, 4 < 5继续 但是2 < 4 故 4 插入2 5之间。

效率:对于长度为N的数组且主键不重复的数组， 平均插入需要_{N^2/4次比较以及}N^{2/4交换。最坏需要~N}2/2次比较和~N^2/2次交换, 最好需要N-1次比较和0次交换

说明:

插入排序

可见红色箭头移动一次累加比较次数：1 + 2 + 3 因为a[j] 都比a[j - 1]小 所以比较次数很多。交换 1 + 2 + 3次。

但是 如果是 【1 2 3 4】 比较 3次 交换0次。

Code

     int a[10] = {4, 2, 5, 7, 8, 9, 10, 1, 6, 3};
    
    for (int i = 1; i < N; i++) {
        
        for (int j = i; j > 0 && a[j] < a[j - 1]; j--) {
            exchange(&a[j], &a[j -1]);
        }
    }

其中N是宏定义的个数， exchange是定义的一个交换函数。j交换以后红色箭头元素会移动， 但是j--。移动一次j--一次， 所以箭头的任然是a[j]初始那个元素。插入排序对部分有序的数组十分高效，也很是很小规模的数组。所以可以让数组先部分有序， 这就减少了比较次数， 提高了效率。所以这就很好理解希尔排序了。

希尔排序

思想:

1. 先部分有序化(任然是小范围插入排序思想)
2. 增量为1时 为 插入排序

效率:希尔排序的时间复杂度会比o(n²)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

说明:
递增序列给出一种:1 4 13 40 ...(3 * h + 1)

增量为4时对以下元素进行部分有序化。

希尔排序增量为4的排序

code

    
     int a[10] = {4, 2, 5, 7, 8, 9, 10, 1, 6, 3};
    
    int h = 1;
    while (h < N/3) h = 3 * h + 1;
    
    while (h >= 1) {
        for (int i = h; i < N; i++) {
            for (int j = i; j >= h && a[j] < a[j - h]; j-=h) {
                exchange(&a[j], &a[j - h]);
            }
        }
        
        h = (h - 1)/3;
        
    }