目录
1. 排序
1.1 概念
1. 排序：所谓排序，就是使一串记录按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
2. 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的，否则称为不稳定的。
3. 内排序：数据元素全部放在内存中的排序。
4. 外排序：在外存中对数据排序。
1.2 常见排序算法
2. 插入排序
2.1 直接插入排序
2.1.1 基本思想
1. 假设有一个空数组，插入第一个数据时不用比较默认有序，插入第二个数据时要和前面数据比较，插入第三个数据时要和前面数据比较...
2. 每次新插入数据就和数组的最后一个数据比较，如果比最后一个数据小就继续往前比较，如果比最后一个数据大就放在该数据的后面。
1. 假设有一个非空无序数组，那么就把第二个元素当作是要插入的元素和第一个比较，这一趟比较完会获得前两个元素有序。
2. 前两个比较完后，就将第三个元素看作是要插入的元素进行一趟比较，比较完后会获得前三个有序。
3. 以此类推，直到把最后一个元素看作是要插入的元素，比较完后就全部有序了。
2.1.2 代码实现
void InsertSort(int* arr, int n) { /*一开始全部无序，就假设第一个元素下标是end，end后面是要插入的数，单趟比较结束后有序的数就多了一个，end就要往后一位， 直到end变成倒数第二个元素的下标，也就意味着只剩最后一个是要插入比较的。*/ for (int i=0; i<n-1; i++) { //1. 一开始设end是第一个元素的下标，tmp是end后一位的元素。 int end = i; int tmp = arr[end + 1]; //2. 如果tmp比arr[end]小，则arr[end]往后挪一位，tmp继续往前比较。 //3. 如果tmp比arr[end]大，则tmp就放在arr[end]后面。 //4. 如果tmp比所有元素都小，tmp会一直往前比直到超出数组范围，此时end减到了-1，tmp放在arr[end+1]位置即可。 while (end >= 0) { if (tmp < arr[end]) { arr[end + 1] = arr[end]; end--; } else break; } arr[end + 1] = tmp; } }
2.1.3 特性
1. 元素集合越接近有序，直接插入排序算法的时间效率越高。
2. 时间复杂度：O(N^2)。
3. 空间复杂度：O(1)。
4. 稳定性：稳定，遇到相等不动，可以保证相对顺序。
2.2 希尔排序(缩小增量排序)
2.2.1 基本思想
1. 先进行多次预排序，预排序之后进行一次直接插入排序。
2. 假设一个gap = 3，将距离为gap的元素分为一组，一共有gap组，对gap组进行插入排序，这就是预排序。
3. 当gap = 1时，这就是直接插入排序。
如图可知，红色为一个gap组，蓝色为一个gap组，绿色为一个gap组。
2.2.2 单个gap组的比较
1. 一个集合被分为多个gap组，这只完成了一个gap组的比较。
int gap = 3; //end只用走到gap组的倒数第二个位置，gap组的倒数第二个和倒数第一个比完就结束了。 for (int i = 0; i < n - gap; i += gap) { //通过end_index找到下一个gap组元素。 int end_index = i; int tmp = arr[end_index + gap]; while (end_index >= 0) { //tmp小，前面的就往后走，tmp继续往前比较。 if (tmp < arr[end_index]) { arr[end_index + gap] = arr[end_index]; end_index -= gap; } //tmp大，就不用比较，已经有序了。 else { break; } } //循环走完了没中断意味着tmp最小，一直往前比到越界了，加回一个gap就是gap组第一个位置。 arr[end_index + gap] = tmp; }
2.2.3 多个gap组比较(一次预排序)
1. 如上图，gap = 3，集合被分成3个gap组，需要进行三次gap组排序。
//在单次gap组比较外面加一层循环，循环gap次。 int gap = 3; for (int j = 0; j < gap; j++) { //end只用走到gap组的倒数第二个位置，gap组的倒数第二个和倒数第一个比完就结束了。 for (int i = 0; i < n - gap; i += gap) { //通过end_index找到下一个gap组元素。 int end_index = i; int tmp = arr[end_index + gap]; while (end_index >= 0) { //tmp小，前面的就往后走，tmp继续往前比较。 if (tmp < arr[end_index]) { arr[end_index + gap] = arr[end_index]; end_index -= gap; } //tmp大，就不用比较，已经有序了。 else { break; } } //循环走完了没中断意味着tmp最小，一直往前比到越界了，加回一个gap就是gap组第一个位置。 arr[end_index + gap] = tmp; } }
多个gap组比较的优化：
1. 上面的代码是将一个gap组排完后再去排另一个gap组。
2. 如图可知不同的gap组之间是连续的，我们可以将不同的gap组轮流排序，你排一个我排一个。
int gap = 3; //end只用走到gap组的倒数第二个位置，gap组的倒数第二个和倒数第一个比完就结束了。 //i每次加一，gap组轮流排序。 for (int i = 0; i < n - gap; i++) { //通过end_index找到下一个gap组元素。 int end_index = i; int tmp = arr[end_index + gap]; while (end_index >= 0) { //tmp小，前面的就往后走，tmp继续往前比较。 if (tmp < arr[end_index]) { arr[end_index + gap] = arr[end_index]; end_index -= gap; } //tmp大，就不用比较，已经有序了。 else { break; } } //循环走完了没中断意味着tmp最小，一直往前比到越界了，加回一个gap就是gap组第一个位置。 arr[end_index + gap] = tmp; }
2.2.4 多次预排序
1. 全部gap组排序完成后叫作一次预排序，事实上我们会通过改变gap的值进行多次预排序。
2. 一般gap的变化是，gap = gap / 3 + 1 或 gap = gap / 2。
void ShellSort(int* arr, int n) { int gap = n; while (gap > 1) { //gap不断变化不断进行预排序，最后一次是1，相当于是直接插入排序，然后就结束。 gap = gap / 3 + 1; //end只用走到gap组的倒数第二个位置，gap组的倒数第二个和倒数第一个比完就结束了。 //i每次加一，gap组轮流排序。 for (int i = 0; i < n - gap; i++) { //通过end_index找到下一个gap组元素。 int end_index = i; int tmp = arr[end_index + gap]; while (end_index >= 0) { //tmp小，前面的就往后走，tmp继续往前比较。 if (tmp < arr[end_index]) { arr[end_index + gap] = arr[end_index]; end_index -= gap; } //tmp大，就不用比较，已经有序了。 else { break; } } //循环走完了没中断意味着tmp最小，一直往前比到越界了，加回一个gap就是gap组第一个位置。 arr[end_index + gap] = tmp; } } }
2.2.5 特性
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会快很多。
3. 希尔排序的时间复杂度不固定，不好计算，一般认为是O(n) = n^1.3。
4. 稳定性：不稳定，被分成不同的gap组无法保证相对顺序。
3. 选择排序
3.1 直接选择排序
3.1.1 基本思想
1. 每一次从待排序的元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的元素排完。
3.1.2 代码实现
1. 找出区间中最小的放到区间第一位。
2. 区间会不断往后缩小。
void SelectSort(int* arr, int n) { int begin = 0; int end = n - 1; //begin等于end的时候不用排 while (begin < end) { int min_i = begin; //遍历完当前区间找出最小元素的坐标。 for (int i = begin; i <= end; i++) { if (arr[i] < arr[min_i]) { min_i = i; } } //和begin交换。 Swap(&arr[begin], &arr[min_i]); //每排完一个begin就可以往后走。 begin++; } }
3.1.3 特性
1. 时间复杂度：O(N^2)
2. 空间复杂度：O(1)
3. 稳定性：不稳定，[5, 1, 2, 5, 1]，这里的1虽然稳定了，但是5不稳定。
3.2 堆排序
推排序详解：【数据结构】二叉树的顺序结构，详细介绍堆以及堆的实现，堆排序-CSDN博客
特性：
1. 时间复杂度：O(N*logN)，n+n*logn，建堆+排序。
2. 空间复杂度：O(1)
3. 稳定性：不稳定。[8, 8, 7, ...]，往后交换就不稳定了。
4. 交换排序
4.1 冒泡排序
4.1.1 基本思想
首先第一个元素9和下一个元素进行比较，9比8大就交换位置，继续9和下一个元素进行比较，直到来到最后或者遇到更大的就停下。这叫一趟冒泡排序。
第二趟将9前面的元素进行排序，10个元素需要9趟，n个元素需要n-1趟。
void BubbleSort(int* arr, int n) { int flag = 1; //只用走n-1趟，最后剩下一个数不用比较。 for (int i = 0; i < n - 1; i++) { //每一趟比较中，也不用走到该趟的最后一个数。 for (int j = 0; j < n-i-1; j++) { if (arr[j] > arr[j + 1]) { flag = 0; Swap(&arr[j], &arr[j + 1]); } } //小优化，如果有一趟没发生比较就证明有序了。 if (flag == 1) { break; } } }
4.1.2 特性
1. 时间复杂度：O(N^2)
2. 空间复杂度：O(1)
3. 稳定性：稳定，遇到相等的不动。
4.2 快速排序
4.2.1 基本思想
1. 任取待排序元素序列中的某元素作为基准值key(一般去左边第一个或右边第一个)。
2. 根据key将待排序集合分成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，这是一趟。
3. 然后子序列重复此过程直到有序。
4.2.2 单趟比较
hoare版本
1. 如图，左边找比key小，右边找比key大，然后左右交换。
2. 最后相遇位置和key交换。
3. 左边做key就右边先走，右边做key就左边先走。
谁先走的问题：
1. 假设右边先走，那么L和R相遇只有两种情况：
情况一：R遇到L，R一直找不到比key小，一直往前走直到遇到L，此时L可能没动过是key的位置，也可能是和R交换后还没动。
情况二：L遇到R，L一直找不到比key大就一直往后走直到遇到R，此时R是遇到比key小停下的。
int PartSort1(int* arr, int left, int right) { //设key是该区间第一个元素的下标。 int key = left; while (left < right) { //右边先开始找比key元素小的。 while (right > left && arr[right] >= arr[key]) { right--; } //右边找完，左边开始找比key元素大的。 while (left < right && arr[left] <= arr[key]) { left++; } //左右交换。 Swap(&arr[left], &arr[right]); } //相遇点和key交换。 Swap(&arr[left], &arr[key]); key = left; return key; }
挖坑法
1. 先把左边第一个元素保存起来当作key，同时左边第一个位置变成坑位。
2. 右边先动，找到比key小的放进坑中，同时自己变成坑。
3. 然后到左边找到比key大的放进坑中，同时自己变成新的坑。交替进行。
4. 最后相遇必是坑，放入key。
int PartSort2(int* arr, int left, int right) { //将左边第一个元素当作key保存起来，同时变成坑位。 int key = arr[left]; int hole = left; while (left < right) { //右边找比key小的放进坑位，然后自己变成坑位。 while (right > left && arr[right] >= key) { right--; } arr[hole] = arr[right]; hole = right; //左边找比key大的放进坑位，然后自己变成坑位。 while (left < right && arr[left] <= key) { left++; } arr[hole] = arr[left]; hole = left; } //相遇时肯定是坑，把key放进坑中，返回相遇位置。 arr[hole] = key; return hole; }
前后指针版本
1. 设key是第一个元素下标，prev在左边第一个位置，cur在prev后面一个位置。
2. cur不断遍历直到元素结束。
3. 当cur位置元素比key大，什么也不做。
4. 当cur位置元素比key小，prev加一，然后cur和prev交换值。
5. 最后cur遍历结束，prev位置和key位置交换值。
int PartSort3(int* arr, int left, int right) { //key是第一个元素下标，prev从第一个位置开始，cur在prev后面。 int key = left; int prev = left; int cur = prev + 1; //cur来遍历 while (cur <= right) { //当cur遇到比key小，prev往前走然后交换。 if (arr[cur] < arr[key]) { prev++; //当一直都比key小的时候，prev和cur会重叠。 if (prev != cur) { Swap(&arr[cur], &arr[prev]); } } cur++; } //最后prev和key交换。 Swap(&arr[prev], &arr[key]); //此时左边比prev小，右边比prev大。 return prev; }
4.2.3 快排递归实现
1. 通过单趟排序划分两块区间，大于key的，小于key的。
2. 不断递归左右区间。
void QuickSort(int* arr, int left, int right) { //递归结束条件, 子序列只有一个值或子序列不存在。 if (left >= right) { return; } //每次单趟排序分出左右子序列，[left, key-1] key [key+1, right]。 int key = PartSort3(arr, left, right); //再对左右子序列进行同样的排序。 QuickSort(arr, left, key - 1); QuickSort(arr, key + 1, right); }
4.2.4 快排优化
三数取中法
原本是默认第一个元素是key，现在优化为三数取中法选key，目的是应对每次key都是最小的情况。
1. 固定两个数，另外一个数分情况比较。
2. 算出三个数的中间值，返回这个中间值的下标。
3. 将这个值交换到key的位置。
int GetMid(int* arr, int left, int right) { int mid = (left + right) / 2; if (arr[left] > arr[mid]) { if (arr[mid] > arr[right]) { return mid; } else if (arr[left] < arr[right]) { return left; } else { return right; } } else { if (arr[left] > arr[right]) { return left; } else if (arr[right] > arr[mid]) { return mid; } else { return right; } } }int PartSort3(int* arr, int left, int right) { //设key在第一个位置，prev从第一个位置开始，cur在prev后面。 int key = left; int prev = left; int cur = prev + 1; //通过三数取中法，选出一个数交换到key中。 int mid = GetMid(arr, left, right); Swap(&arr[key], &arr[mid]); //cur来遍历 while (cur <= right) { //当cur遇到比key小，prev往前走然后交换。z if (arr[cur] < arr[key]) { prev++; //当cur一直都比key小的时候，prev和cur会重叠。 if (prev != cur) { Swap(&arr[cur], &arr[prev]); } } cur++; } //最后prev和key交换。 Swap(&arr[prev], &arr[key]); key = prev; return key; }
4.2.5 快排非递归实现
1. 思想：利用栈存储区间的下标，通过出栈入栈控制下标区间的排序。
2. 先存入初始区间的下标，出栈获得下标进行单趟排序，又重新获得两个子区间的下标入栈。
3. 栈就是媒介，用来保存下标。利用后进先出可以让后面进来的下标先排序。
void QuickSortNonR(int* arr, int left, int right) { //利用栈实现 Stack st; StackInit(&st); //先将初始的区间入栈 StackPush(&st, right); StackPush(&st, left); while (!StackEmpty(&st)) { //出栈获得区间下标进行单趟排序 int left = StackTop(&st); StackPop(&st); int right = StackTop(&st); StackPop(&st); //[left, key-1] key [key+1, right] int key = PartSort3(arr, left, right); //将分割好的区间继续入栈，等下次出栈排序 //先入右边再入左边 //当区间只有一个元素或区间不存在就不入栈。 if (key + 1 < right) { StackPush(&st, right); StackPush(&st, key + 1); } if (left < key - 1) { StackPush(&st, key - 1); StackPush(&st, left); } } StackDestroy(&st); }
4.2.6 特性
1. 空间复杂度O(n) = logn(2为底)，不断递归会不断建立栈帧，一共有logn层。
2. 时间复杂度O(n) = n*logn(2为底)，一共logn层递归，每层消耗n。
3. 稳定性：不稳定
4.2.7 三路划分
1. 三路划分应对当很多值都等于key的时候。
void QuickSort(int* arr, int left, int right) { //递归结束条件, 子序列只有一个值或子序列不存在。 if (left >= right) { return; } //三路划分分出左右子序列，[left, key1-1] [key1, key2] [key2+1, right]。 int key = arr[left]; int key1 = left; int key2 = right; int cur = left + 1; //遇到小的放左边，大的放右边，相等的跳过。 while (cur <= key2) { if (arr[cur] < key) { Swap(&arr[cur], &arr[key1]); key1++; cur++; } else if (arr[cur] > key) { Swap(&arr[cur], &arr[key2]); key2--; } else { cur++; } } //再对左右子序列进行同样的排序。 QuickSort(arr, left, key1 - 1); QuickSort(arr, key2 + 1, right); }
5. 归并排序
5.1 递归实现
1. 将区间从中间平分得到两个子区间，利用后序思想不断分化区间直到区间只剩一个数。
2. 当区间分化完后再回来归并。
3. 利用临时数组归并然后拷贝回原数组。
1. 将区间从中间平分得到两个子区间，利用后序思想不断分化区间直到区间只剩一个数。
2. 当区间分化完后再回来归并。
3. 利用临时数组归并然后拷贝回原数组。
4. 因为取区间的中间下标向下调整了，所以不会出现区间不存在的情况，最终都只会是区间只有一个数。
void _MergeSort(int* arr, int begin, int end, int* tmp) { //递归结束条件:只有一个数。 if (begin == end) { return; } //将区间平分[begin, mid] [mid+1, end] int mid = (begin + end) / 2; _MergeSort(arr, begin, mid, tmp); _MergeSort(arr, mid + 1, end, tmp); //归并，对两个区间进行排序插入临时数组中。 int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int tmp_i = begin; while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] <= arr[begin2]) { tmp[tmp_i] = arr[begin1]; tmp_i++; begin1++; } else { tmp[tmp_i] = arr[begin2]; tmp_i++; begin2++; } } while (begin1 <= end1) { tmp[tmp_i] = arr[begin1]; tmp_i++; begin1++; } while (begin2 <= end2) { tmp[tmp_i] = arr[begin2]; tmp_i++; begin2++; } //归并一段，拷贝一段，根据开始的位置拷贝回去。 memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1)); } // 归并排序递归实现 void MergeSort(int* arr, int n) { //临时数组用来归并 int* tmp = (int*)malloc(sizeof(int) * n); //传入区间的下标。 _MergeSort(arr, 0, n - 1, tmp); free(tmp); }
5.2 特性
1. 时间复杂度：O(N*logN)，一共会递归logN层，每层消耗N。
2. 空间复杂度：O(N)，开了临时数组，递归建立栈帧也有消耗logN不过可以忽略。
3. 稳定性：稳定，相等的时候控制左区间先尾插入数组。
4. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
5.3 非递归实现
思想：
1. 利用循环遍历归并区间，利用gap控制区间个数。
void MergeSortNonR(int* arr, int n) { int* tmp = (int*)malloc(sizeof(int) * n); //遍历数组进行归并，区间的个数是gap。 //gap表示区间个数，每次归并两个区间，区间个数从1开始，每次归并完会呈2倍增长。1，2，4... for (int gap = 1; gap < n; gap *= 2) { int tmp_i = 0; for (int i = 0; i < n; i += gap * 2) { //归并区间的下标 int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; //归并 while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] <= arr[begin2]) { tmp[tmp_i] = arr[begin1]; tmp_i++; begin1++; } else { tmp[tmp_i] = arr[begin2]; tmp_i++; begin2++; } } while (begin1 <= end1) { tmp[tmp_i] = arr[begin1]; tmp_i++; begin1++; } while (begin2 <= end2) { tmp[tmp_i] = arr[begin2]; tmp_i++; begin2++; } //归并一段，拷贝一段。 memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1)); } } free(tmp); }修正：
1. 上面的代码只适用于数组个数是2的倍数的情况，其他个数会有三种越界情况。
3. 因为gap每次都是二倍增长，所以单纯使用gap来定义下标会造成超过原数组。
3. 如图，有两种情况最后是凑不出两个区间归并的，我们就不归并，还有一种是最后能凑出两个区间，只不过最后一个区间比较小，我们就把最后一个下标手动调整到数组最后一位即可。
void MergeSortNonR(int* arr, int n) { int* tmp = (int*)malloc(sizeof(int) * n); //遍历数组进行归并，区间的个数是gap。 //gap表示区间个数，每次归并两个区间，区间个数从1开始，每次归并完会呈2倍增长。1，2，4... for (int gap = 1; gap < n; gap *= 2) { int tmp_i = 0; for (int i = 0; i < n; i += gap * 2) { //归并区间的下标 int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; //判断下标是否合法 //最后这一组归并凑不出两个区间就直接不归并了。 if (end1 >= n || begin2 >= n) { break; } //通过gap算出的第二个区间的下标越界了，就手动把下标缩减。 if (end2 >= n) { end2 = n - 1; } //归并 while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] <= arr[begin2]) { tmp[tmp_i] = arr[begin1]; tmp_i++; begin1++; } else { tmp[tmp_i] = arr[begin2]; tmp_i++; begin2++; } } while (begin1 <= end1) { tmp[tmp_i] = arr[begin1]; tmp_i++; begin1++; } while (begin2 <= end2) { tmp[tmp_i] = arr[begin2]; tmp_i++; begin2++; } //归并一段，拷贝一段。 memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1)); } } free(tmp); }第二种拷贝方法：
如果你想每层gap归并完再拷贝，你就需要改变以下修正。
2. end1越界：那么你就把end1改成数组最后一位，第二个区间改成不存在，这样子可以复用下面的while，就是单纯的把当前区间尾插到tmp中。
3. begin2越界：那直接把第二个区间改不存在，第一个区间走下面的循环直接尾插tmp。
4. end2越界：这个把end2改成数组最后一位，可以凑成两个区间。
5.4 小区间优化
1. 当递归分化的区间个数小于10时，可以使用直接插入排序。
2. 适用于快排和归并。
3. 当个数小于10不递归可以减少最后三层递归，以满二叉树为例，总节点有2^h - 1，最后三层节点有2^(h-1) + 2^(h-2) + 2^(h-3)，已经占了总节点的%80了。
//当分化的区间个数小于10就使用直接插入排序。 if (end - begin + 1 < 10) { //传入区间的开始位置和区间的个数。 InsertSort(arr + begin, end - begin + 1); return; }
5.5 外排序
1. 外排序是在外存对数据进行排序，这里用到归并排序的思想。
2. 假设有一个40G的文件，但只有1G内存。需要先把文件分成40个1G的小文件，然后在内存中把1G的小文件内容排序好，接着在外存中对文件进行归并。40个有序的小文件不断归并成大文件。
6. 计数排序
6.1 基本思想
1. 统计每个元素个数。
2. 根据元素个数在原数组写入。
3. 利用相对映射实现下标对应。最小值减最小值就是0，每个数都去减最小值就是下标。
4. 最大值减最小值求出个数来确定统计数组要开多大空间。
void CountSort(int* arr, int n) { int max = arr[0]; int min = arr[0]; //遍历找出最大值和最小值。 for (int i = 1; i < n; i++) { if (arr[i] < min) { min = arr[i]; } else if (arr[i] > max) { max = arr[i]; } } //算出统计数组要开多大。 int size = max - min + 1; int* count_arr = (int*)malloc(sizeof(int) * size); //利用相对映射，元素出现一次就加一次。 for (int i = 0; i < n; i++) { count_arr[arr[i] - min]++; } //遍历统计的数组，原数组就按顺序写。 int arr_i = 0; for (int i = 0; i < size; i++) { //统计的次数有多少次就写多少次。 //下标加回最小值就是原本的数值。 while (count_arr[i]) { arr[arr_i] = i + min; arr_i++; count_arr[i]--; } } }
6.2 特性
1. 时间复杂度：O(max(n, size))，有两个数组遍历，不确定大小关系。
2. 空间复杂度：O(size)，统计数组的空间。
3. 缺点：只能比较整型，适用范围集中的数组。
4. 稳定性：稳定。
7. 选择题
1. 快速排序算法是基于（ ）的一个排序算法。
A分治法
B贪心法
C递归法
D动态规划法
答：A
2.对记录（54,38,96,23,15,72,60,45,83）进行从小到大的直接插入排序时，当把第8个记录45插入到有序表时，为找到插入位置需比较（ ）次？（采用从后往前比较）
A 3
B 4
C 5
D 6
答：C
3.以下排序方式中占用O（n）辅助存储空间的是
A 简单排序
B 快速排序
C 堆排序
D 归并排序
答：D
4.下列排序算法中稳定且时间复杂度为O(n2)的是（ ）
A 快速排序
B 冒泡排序
C 直接选择排序
D 归并排序
答：B
5.关于排序，下面说法不正确的是
A 快排时间复杂度为O(N*logN)，空间复杂度为O(logN)
B 归并排序是一种稳定的排序,堆排序和快排均不稳定
C 序列基本有序时，快排退化成冒泡排序，直接插入排序最快
D 归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN)
答：D
6.下列排序法中，最坏情况下时间复杂度最小的是（ ）
A 堆排序
B 快速排序
C 希尔排序
D 冒泡排序
答：A
7.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)，则以第一个关键字65为基准而得到的一趟快速排序结果是（）
A 34，56，25，65，86，99，72，66
B 25，34，56，65，99，86，72，66
C 34，56，25，65，66，99，86，72
D 34，56，25，65，99，86，72，66
答：A
完整代码：Sort/Sort/Sort.c · 林宇恒/DataStructure - 码云 - 开源中国 (gitee.com)
标签：arr,end,int,堆排序,gap,快排,key,排序 From： https://blog.csdn.net/m0_71164215/article/details/141437531