1. 排序算法
1.1 算法的之间的比较
| 排序算法 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 数据对象稳定性 |
| 冒泡排序 | O(n2) | O(n2) | O(1) | 稳定 |
| 选择排序 | O(n2) | O(n2) | O(1) | 数组不稳定、链表稳定 |
| 插入排序 | O(n2) | O(n2) | O(1) | 稳定 |
| 快速排序 | O(n*log2n) | O(n2) | O(log2n) | 不稳定 |
| 堆排序 | O(n*log2n) | O(n*log2n) | O(1) | 不稳定 |
| 归并排序 | O(n*log2n) | O(n*log2n) | O(n) | 稳定 |
| 希尔排序 | O(n*log2n) | O(n2) | O(1) | 不稳定 |
| 计数排序 | O(n+m) | O(n+m) | O(n+m) | 稳定 |
| 桶排序 | O(n) | O(n) | O(m) | 稳定 |
| 基数排序 | O(k*n) | O(n2) | O(k+n) | 稳定 |
1.2 冒泡排序
算法思想
- 比较相邻的元素，如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从第一对开始，一直到最后一对，做完后，最后的元素会是最大的元素。
- 针对所有的元素重复上面的步骤，除排序好的。
- 持续对越来越少的元素重复上述步骤，直到哪次没有任何一对数字需要比较或者是交换。
图解
代码
void bubbleSort(int a[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; ++j) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); } } } }
1.3 选择排序
算法思想
- 在未排序的序列中找到最小（大）元素，存放到排序序列的起始位置。
- 从剩下未排序元素中继续寻找最小（大）元素，然后放到自己已排序的序列的末尾。
- 以此类推，直到所有元素排序完毕。
图解
代码
void selectionSort(int a[], int len) { int min; for (int i = 0; i < len - 1; i++) { min = i; for (int j = i + 1; j < len; j++) { if (a[j] < a[min]) { min = j; } } swap(a[i], a[min]); } }
1.4 插入排序
算法思想
- 从第一个元素开始，该元素可以认为已经被排序。
- 取出下一个元素，在已经排序的元素序列中从后向前扫描。
- 如果该元素（已排序）大于新元素，该元素移到下一个位置。
- 重复步骤3，直到找到已排序的元素小于或者等于新的元素的位置。
- 将元素插入到对应位置。
- 重复2~5。
图解
代码
void InsertSort(int a[], int n) { for (int i = 1; i < n; i++) { if (a[i] < a[i - 1]) { int val = a[i]; int j = i - 1; a[j + 1] = a[j]; while (j > 0 && val < a[j - 1]) { a[j] = a[j - 1]; j--; } a[j] = val; } } }
1.5 快速排序
算法思想
- 选第一个数为标准。
- 将比基准小的数据交换到前面，比基准大的交换到后面
- 对左边的空间和右边的空间重复，直到各区间只有一个数字
图解
代码
void QuickSort(int a[], int left, int right) { if (left >= right) return; int begin = left; int end = right; //keyi定在右边，需要从左边开始找 int keyi = end; int key = a[keyi]; while (begin < end) { //因为我们从小往大排 //从左边开始找 找大 while (begin < end && a[begin] <= key) begin++; a[end] = a[begin]; //从右边开始找 找小 while (begin < end && a[end] >= key) end--; a[begin] = a[end]; } a[end] = key; QuickSort(a, left, end - 1); QuickSort(a, end + 1, right); }
1.6 堆排序
算法思想
- 如果要从小到大排序，建立大堆，根节点大于左右子树。
- 将根结和最后一个元素交换，并且树的元素个数减1。
- 重复1~2，直到只剩一个元素。
图解
代码
void AdjustDown(int* a, int n, int root)//n是大小，root是根节点的下标 { int parent = root; int child = parent * 2 + 1; while (child < n) { //child指向左右孩子中最小的那个 if (child + 1 < n && a[child + 1] < a[child]) { child++; } if (a[child] < a[parent]) { swap(a[child], a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void HeapPop(Heap* php) { assert(php); assert(php->size > 0); swap(&php->a[0], &php->a[php->size - 1]); php->size--; AdjustDown(php->a, php->size, 0); }
1.7 计数排序
算法思想
- 找出待排序的数组最大和最小的元素
- 统计数组中每个值为i的元素出现的个数，存入数组c的第i-min项
- 将下标+min的值根据在数组c中的个数存到原数组中。
图解
代码
void CountSort(int a[], int len) { int max = a[0]; int min = a[0]; for (int i = 0; i < len; i++) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } int l = max - min;//计算数组最大最小值的差 int* count_a = new int[l + 1]; for (int i = 0; i < l + 1; i++) { count_a[i] = 0; } for (int i = 0; i < len; i++) { count_a[a[i] - min]++;//统计元素个数 } int j = 0; for (int i = 0; i < len; i) { while (j <= l && count_a[j]) { count_a[j]--; a[i] = j + min; i++; } j++; } }
1.8 桶排序
算法思想
- 设置一个定量的数组当作空桶；
- 遍历输入数据，并且把数据一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序；
- 从不是空的桶里把排好序的数据拼接起来。
图解
1.9 基数排序
算法思想
- 取得数组中的最大数，并取得位数。
- arr为原始数组，从最低位开始取每个位组成radix数组。
- 对radix进行计数排序（利用计数排序适用于小范围数的特点）。
图解
1.10 希尔排序
算法思想
- 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk = 1。
- 按照增量序列个数k，对序列进行k趟排序
- 每趟排序根据对应的增量ti，将待排序的序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。
图解
代码
void ShellSort(int* a, int n) { printf("原数组->", gap); PrintArray(a, n); int gap = n;//间隔 while (gap > 1) { gap = gap / 3 + 1;//保证最后一趟一定为1 for (int i = 0; i < n - gap; i++) { int end = 0; int tmp = a[end + gap]; while (end >= 0) { if (tmp < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } printf("gap:%d->", gap); PrintArray(a, n); } }
1.11 归并排序
算法思想
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
图解
代码
void _MergeSort(int* a, int left, int right, int* tmp) { if (left == right) return; //int mid = (left + right) >> 1;//有溢出风险 int mid = left + ((right - left) >> 1); _MergeSort(a, left, mid, tmp); _MergeSort(a, mid + 1, right, tmp); int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int i = begin1; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } //拷回原数组 int j = left; while (j <= right) { a[j] = tmp[j]; j++; } } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int)*n); _MergeSort(a, 0, n - 1, tmp); free(tmp); }
