三种基本排序算法的实现

1.选择排序

选择排序是一种简单直观的排序算法。其原理可以概括为：

  1. 遍历数组：从未排序的序列中选择最小（或最大）的元素。
  2. 交换位置：将该元素与序列的第一个元素（或未排序部分的第一个元素）进行交换，将其放置在已排序部分的末尾。
  3. 重复步骤：重复以上步骤，直到所有元素都被排序完毕。

这样，每一次迭代都会选择未排序部分的最小（或最大）元素，依次放置在已排序部分的末尾，直到整个数组都被排序完成。因此，选择排序的时间复杂度是O(n^2)，其中n是元素的数量。虽然它的时间复杂度较高，但由于其简单性，对于小型数据集来说是一个不错的选择。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
>// 选择排序
>void selection_sort(int arr[], int len) {
   /*
   * i表示未排序序列的开头元素
   * 最后一轮选择排序时, 未排序序列的开头元素是数组倒数第二个元素
   * i的每个取值都表示一轮选择排序
   * 也就是选择排序一共执行9趟
   */ 
   for (int i = 0; i < len - 1; i++) {
       // 不妨直接假设未排序序列的开头i位置元素就是最小值
       int min_index = i;
       // 遍历未排序数组序列,找出真正的最小值下标,此时应遍历最后一个元素
       for (int j = i + 1; j < len; j++) {
           if (arr[j] < arr[min_index]) {
               min_index = j;  // 记录较小值的下标
           }
       }   // for循环结束时，未排序序列的最小值下标就是min_index

       // 交换min_index和下标i的元素
       SWAP(arr, min_index, i);
       // 选择排序一趟打印一次数组
       print_arr(arr, len);
   }
>}

2.冒泡排序

冒泡排序是一种简单直观的排序算法，其原理可以概括为：

  1. 比较相邻元素：从数组的起始位置开始，依次比较相邻的两个元素。
  2. 交换位置：如果相邻元素的顺序不符合排序规则（比如升序排序要求前面的元素小于后面的元素），则交换它们的位置。
  3. 重复步骤：重复以上步骤，直到没有需要交换的元素，即整个数组都已经按照排序规则排列好。

这样，每一次迭代都会将当前未排序部分的最大元素交换到正确的位置，直到整个数组都被排序完成。冒泡排序的时间复杂度也是O(n^2)，其中n是元素的数量。尽管它在大型数据集上性能较差，但由于其简单易懂的特点，它常被用于教学和理解排序算法的基本原理。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
>void bubble_sort(int *num,int len) {
for (int i = 0; i < len; ++i) {
	for (int j = len - 1; j > i; --j) {
		if (num[j] < num[j - 1]) {
			swap(&num[j], &num[j - 1]);
		}
	}
	print_num(num, len);
}

>}

上述实现仍然有优化的空间，例如，如果某一趟冒泡排序没有交换任何元素，那么说明数组已经全部有序了，就直接退出即可。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
>void bubble_sort(int arr[], int len) {
   // 外层for的i表示第几轮冒泡排序,最多需要进行len-1轮
   for (int i = 1; i < len; i++) {
       // 标记在这一次冒泡排序中有没有交换,false表示没有交换
       bool swapped = false;
       /*
       * j表示两两比较元素中的第一个元素的下标
       * 第一轮j的最大取值是数组倒数第二个元素,并且逐步减小
       * 所以j的条件是小于 (len - i)
       */ 
       for (int j = 0; j < len - i; j++) {
           if (arr[j] > arr[j + 1]) {
               SWAP(arr, j, j + 1);
               // 发生了交换改变标记
               swapped = true;
           }
       }
       // 在一轮冒泡排序中没有任何交换,则排序已经完成,终止循环
       if (!swapped) {
           break;
       }
   // 打印一轮冒泡排序后数组的元素排列
       print_arr(arr, len);
   }
>}

3.插入排序

插入排序是一种简单直观的排序算法，其原理可以概括为：

  1. 分为已排序和未排序部分：将数组分为两部分，一部分是已排序的元素，另一部分是未排序的元素。
  2. 逐步将未排序元素插入已排序部分：从未排序部分取出一个元素，将它插入到已排序部分的正确位置。
  3. 重复步骤：重复上述过程，直到未排序部分的所有元素都被插入到已排序部分。

具体来说，插入排序每次将未排序部分的第一个元素插入到已排序部分的合适位置，确保已排序部分始终是有序的。这样，每一轮迭代都会使已排序部分增加一个元素，最终使整个数组都被排序完成。

插入排序的时间复杂度也是O(n^2)，其中n是元素的数量。尽管与选择排序和冒泡排序有相同的时间复杂度，但在实际应用中，插入排序通常比它们快，特别是在数据已经基本有序的情况下。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
//插入排序
void insert_sort(int *num,int len){
	for (int i = 0; i < len-1; ++i) {
		for (int j = i + 1; j > 0; --j) {
			if (num[j] < num[j - 1]) {
				swap(&num[j],&num[j-1]);
			}
		}
		print_num(num,len);
	}
}

上述实现仍然有优化空间，例如每次要把元素从i+1的位置置换到目标位置的时候，途径的元素都需要进行置换，而置换需要三次赋值操作，所以可以把这个过程给优化掉，思路为记录i+1位置元素的值，然后if条件满足的时候，不进行置换，而是进行赋值，将途径位置的元素统统往后移动一个位置，最后将记录的值放在目标位置即可，这样将每个途经元素都要进行三次赋值减少为了只需要赋值一次。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void optimized_insertion_sort(int arr[], int len) {
    // 外层for循环中的i表示每轮选择排序新插入元素的下标,也就是"新摸手牌"的下标
    for (int i = 1; i < len; i++){
        /*使用while实现
        // 新插入的元素存储起来
        int temp = arr[i];
        // j代表新插入元素前面元素的下标,也就是"老手牌"的下表
        int j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            // 将新插入元素前面的元素向后移动一位
            arr[j + 1] = arr[j];
            j--;
        }
        */
    // 上面的while循环可以改成for循环
    for (int j = i - 1; j >= 0; j--) {
        if (arr[j] > temp) {
        arr[j + 1] = arr[j];
        } else {
        // 当 arr[j] 不再大于 temp 时，跳出循环
        break;
        }
        }
        /*
        * while/for循环结束时, 要么j = -1, 要么arr[j] <= temp
        * 不管是哪种情况。temp最终都需要放入下标j + 1的位置
        */
        arr[j + 1] = temp;

        // 打印每一轮选择排序后,数组的元素序列
        print_arr(arr, len);
    }
}

拓展

希尔排序

希尔排序是插入排序的一种改进版本，也被称为“缩小增量排序”。其原理可以概括为：

  1. 确定增量序列：选择一个增量序列（通常是逐渐减小的序列），用于确定每次比较的间隔。
  2. 按增量分组插入排序：将数组按照指定的增量分成若干个子序列，对每个子序列进行插入排序。
  3. 逐步缩小增量：重复上述步骤，每次减小增量，直到增量为1。
  4. 最终排序：当增量减小至1时，整个数组已经基本有序，此时再进行一次插入排序即可完成最终的排序。

希尔排序的关键在于增量序列的选择，不同的增量序列会导致不同的性能。常见的增量序列有希尔增量序列（如Knuth序列）、Sedgewick增量序列等。

相比于简单的插入排序，希尔排序在初始阶段以较大的步长进行排序，能够更快地将较小的元素移动到正确的位置，从而加速整体排序过程。尽管希尔排序的时间复杂度没有一个确定的数学表达式，但其平均时间复杂度约为O(n log n)到O(n^2)之间，取决于增量序列的选择。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
void print_arr(int arr[], int len) {
  for (int i = 0; i < len; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

void shell_sort(int arr[], int len) {
  int gap = len >> 1;
  // 增量序列大于0就继续进行希尔排序
  while (gap > 0) {
    // 希尔排序就是根据增量不同进行多次插入排序罢了
    // gap在for循环里表示插入排序待插入元素的下标(也就是新摸的手牌)
    // 当gap=1时，就是一个普通插入排序
    for (int i = gap; i < len; i++) {   // 这个i没有必要i+=gap,因为第一个摸到的牌是gap，第二个人摸到的是gap+1....

      // 用一个temp记录待插入元素
      int temp = arr[i];
      // j代表同一个分组内插入排序需要比较的前面元素的下标
      int j = i - gap;
      // 内层循环实现插入排序的逻辑,只要j元素存在且j元素大于后面的待插入元素,就向后移动元素
      while (j >= 0 && arr[j] > temp) {
        // 将"旧手牌"向后移动增量gap个位置
        arr[j + gap] = arr[j];
        // gap增量用于分组,所以j一次性减少gap增量
        j -= gap;
      }

      // 上面一段改成for循环
      int temp = arr[i];
      for (int j = i - gap; j >= 0; j -= gap) {
        if (arr[j] > temp) {
          arr[j + gap] = arr[j];
        } else {
         break;
        }
      }

      // 上面while循环结束时,要么j是一个负数了,要么j位置的元素小于等于temp
      // 不论是哪一种情况,都意味着需要将j的下一个gap位置插入temp
      arr[j + gap] = temp;
    }
    // 每希尔排序一轮,增量减半
    gap >>= 1;
    // 打印每一轮希尔排序后的数组元素
    print_arr(arr, len);
  }
}