写在前面

十大排序

推荐学习的程度:

冒泡排序 ■■□□□
快速排序 ■■■■■
插入排序 ■■■□□
希尔排序 ■□□□□
归并排序 ■■■■■
选择排序 ■■□□□
堆排序 ■■■■□
计数排序 ■■□□□
基数排序 ■□□□□
桶排序 ■□□□□

简单交换排序

定义

简单交换排序是指通过不断比较和交换，将序列中的元素按要求排列成有序序列。每次从未排序区间中选出最小（或最大）元素，交换到当前排序区间的末尾（或开头）。

实现思路

1. 第1轮：找到最小值，放到第1个位置。
2. 第2轮：在剩下的元素中找到最小值，放到第2个位置。
3. 依次类推，直到排序完成。

如下图所示：
数组{9，1，8，5，3}下标 i = 1 元素和下标 i = 2，3，4，5元素比较，如果下标 i = 1 元素比下标 i = 2，3，4，5元素大，交换元素。数组下标 i = 2 元素和下标 i = 3，4，5元素比较...最终最大的元素会到数组末尾。

C语言实现

#include <stdio.h>

#define MAXSIZE 5

typedef struct {
  int array[MAXSIZE + 1]; /* 排序数组， array[0] 用作哨兵或临时变量 */
  int length;
} SqList;

void swap(SqList *L, int i, int j) {
  int temp = L->array[i];
  L->array[i] = L->array[j];
  L->array[j] = temp;
}

void BubbleSort(SqList *L) {
  int i, j;

  for (i = 1; i < L->length; i++) {
    for (j = i + 1; j <= L->length; j++) {
      if (L->array[i] > L->array[j]) {
        swap(L, i, j);
      }
    }
  }
}

int main(void) {
  SqList L;
  int i;
  L.length = 5;

  L.array[1] = 9;
  L.array[2] = 1;
  L.array[3] = 5;
  L.array[4] = 8;
  L.array[5] = 3;

  for (i = 1; i <= L.length; i++) {
    printf("%d ", L.array[i]);
  }
  printf("\n");

  BubbleSort(&L);

  printf("排序后的数组为：");
  for (i = 1; i <= L.length; i++) {
    printf("%d ", L.array[i]);
  }
  printf("\n");

  return 0;
}

9 1 5 8 3 
排序后的数组为：1 3 5 8 9 

[Done] exited with code=0 in 0.412 seconds

复杂度

时间复杂度：O(n²)
空间复杂度：O(1)

冒泡排序

定义

冒泡排序（Bubble Sort） 是一种通过重复比较相邻元素并交换，将较大的元素逐步“冒泡”到序列末尾的排序算法。每一轮都把未排序区间中的最大值移到最后，直到整个序列有序。
动图演示：

实现思路

1. 从头到尾依次比较相邻元素，发现逆序就交换。
2. 每一轮结束后，最大的元素移动到末尾。
3. 重复上述过程，直到所有元素有序。

如下图所示：i = 1 的时候，和 j = 2 （j = i + 1）的元素比较，元素大的往上移，依次相邻元素比较，最终将大的元素逐步移到末尾。 i = 2,3...同理。

注：为了避免像序列{2，1，3，4，5，6，7，8，9}这种，只有前两个序列倒序，后面都是正序，会造成不需要的排序比较的情况，加入一个 flag 标志，当没有出现交换顺序的动作的时候，说明是正序，不需要在经行循环。

C语言实现

#include <stdio.h>

#define MAXSIZE 5
#define TRUE 1
#define FALSE 0

typedef int Status;

typedef struct {
  int array[MAXSIZE + 1]; // array[0] 可作哨兵或临时变量
  int length;
} SqList;

void swap(SqList *L, int i, int j) {
  int temp = L->array[i];
  L->array[i] = L->array[j];
  L->array[j] = temp;
}

void BubbleSort(SqList *L) {
  int i, j;
  Status flag = TRUE;

  for (i = 1; i < L->length && flag; i++) 
  {
    flag = FALSE;

    for (j = 1; j <= L->length - i; j++) 
    {
      if (L->array[j] > L->array[j + 1]) {
        swap(L, j, j + 1);
        flag = TRUE;
      }
    }
  }
}

int main(void) {
  SqList L;
  int i;
  L.length = 5;

  L.array[1] = 9;
  L.array[2] = 1;
  L.array[3] = 5;
  L.array[4] = 8;
  L.array[5] = 3;

  printf("原始数组：");
  for (i = 1; i <= L.length; i++) {
    printf("%d ", L.array[i]);
  }
  printf("\n");

  BubbleSort(&L);

  printf("排序后的数组为：");
  for (i = 1; i <= L.length; i++) {
    printf("%d ", L.array[i]);
  }
  printf("\n");

  return 0;
}

原始数组：9 1 5 8 3 
排序后的数组为：1 3 5 8 9 

[Done] exited with code=0 in 0.417 seconds

复杂度

最好情况：排序表本身有序，需要 n-1 次比较，时间复杂度O(n);
最坏情况：排序表是逆序，需要比较(n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ O(n²)