408排序

1. 插入排序

从左到右，选每个元素插入到前面已排好序的数组中

for (int i = 1; i < N; i++)
{
	if(A[i] < A[i-1]) 
	{	
		int temp = A[i];	
		for (int j = i - 1; j >= 0 && A[j] > temp ; j--)
		{
			A[j+1] = A[j];
		}
		A[j+1] = temp;
	}
}

2. 希尔排序

让数组先局部有序再整体有序，先让间隔 H 的有序(从 h 开始插入前面同组中，同组的前面元素已经有序)，逐步缩小 H 最终让数组完全有序

for (int i = h; i < N; i++)
	{
		for (int j = i; j >= h; j -= h) // 从 h 开始插入排序了，h同组的前面元素已经排好序了
		{
			if (a[j - h] > a[j])
			{
				myswap(a, j, j - h);
			}
		}
  }

如果直接让 d = 1 变成插入排序，时间复杂度变成 $O (n^{2})$ ，正常 $O (n^{1.3})$ ，是一种不稳定的排序算法(快希选堆都不稳定)

3. 冒泡排序

每轮将最小元素冒泡到最左侧

void bubble_sort(int arr[], int size) {
  for (int i = 0; i < size - 1; i++) {
	bool flag = false;
    for (int j = size - 1; j > i;j--) {
      if (arr[j] < arr[j-1]) {
         swap(arr[j],arr[j-1]);  // 把最小的冒泡到最左边
         flag = true;
      }
    }
    if(flag == false) return;
  }
}

空间复杂度: $O (1)$
最坏(平均)时间复杂度 : $0 (n^{2})$

4. 快速排序

void quicksort(int* a, int left,int right)
{
	if (left > right)
		return;
	int tmp = a[left];
	int i = left;
	int j = right;
	while (i < j) { // 所有小于等于的都要放到 pivot 左侧，大于的放在右侧。
		while (a[j] >= tmp && j > i)
			j--;
		while (a[i] <= tmp && j > i)
			i++;
		if (j > i) {
			int t = a[i]; // 此时 i j交换，即让元素去 pivot 对应的一侧
			a[i] = a[j];
			a[j] = t;
		}
	}
	a[left] = a[i];  // 交换 pivot 到 i 位置
	a[i] = tmp;
	quicksort(a, left, i - 1);
	quicksort(a, i + 1, right);
}

5. 选择排序

5.1 简单选择排序

每一次选出最小的值放在最左侧

for(int i = 0;i<N;i++)
{
	int min = i;
	for(int j = i+1;j<N;j++)
	{
		if(arr[min] > arr[j]) min = j;
	}
	if(min != i) swap(arr[i],arr[min]);
}

空间复杂度 O(1)
时间复杂度 $1 + 2 + . . . + (n - 1) = (n - 1) * n / 2$