目录

2.5 冒泡排序

2.6 快速排序

2.6 1 快速排序思路

详细步骤

2.6 2 快速排序递归实现 

2.6 3快速排序非递归：

快排非递归的优势

 非递归思路

1. 初始化栈

2. 将整个数组的起始和结束索引入栈

3. 循环处理栈中的子数组边界

4. 单趟排序

5. 处理分区后的子数组

6. 重复步骤3和步骤5

注意事项

2.7 归并排序

基本思想：

一、算法步骤

二、具体实现

归并排序递归实现：

归并排序非递归实现： 

三、性能分析

2.8 计数排序

计数排序概念：

一、计数排序的原理与步骤

二、计数排序的示例

 计数排序代码实现：

三、注意事项

四、计数排序的特点

---

2.5 冒泡排序

   基本思路：

    冒泡排序的基本思路是通过重复遍历待排序的数列，比较每对相邻元素的值，若发现顺序错误则交换它们的位置。这个过程重复进行，直到没有需要交换的元素为止，此时数列就完成了排序。冒泡排序的名字是因为较小的元素会逐渐“冒泡”到数列的顶端，即前面，而较大的元素则会沉到数列的底部，即后面。
冒泡排序的基本步骤如下：
（1）比较相邻的元素。如果第一个比第二个大，就交换它们两个。
（2）对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
（3）针对所有的元素重复以上的步骤，除了最后一个。
（4)持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
冒泡排序的时间复杂度在最坏情况下是O(n^2)，其中n是数列的长度。尽管冒泡排序不是最高效的排序算法，但它的实现简单，对于小数据量的排序问题还是相当实用的。

  动图展示：

代码实现：

void BubbleSort(int* a, int n)
{for (int i = 1; i < n-1; i++){int flag = 0;for (int j = 0; j < n - i ; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);flag = 1;}}if (flag == 0){break;}}
}

 问：程序中的flag的作用是什么？

答：冒泡排序时间复杂度是O（N^2），但是这个时间复杂度是由这个算法的最坏情况决定的，也就是当我们要排升序时，我们给了一个降序的数组，这时这个程序的时间复杂度就是O（N^2），而在这个组相对有序的情况下 ，我们可以使用一些手段来提高这个算法的效率，而这个flag就是我们优化这个算法的关键。

   我们知道，如果一个相对有序甚至有序组因该是比无序的数组排序的速度更快的，但是，我们需要判断何时有序，像这个程序中我们使用了两个for循环，如果不判断何时有序然后结束程序的话，它就会完完整整地将这两个循环走完，也就是说，无论是有序还是无序的一组数来排序它的时间复杂度都是O（N^2）。这时我们就可以定义一个flag变量，将它初始化为0，如果里面有数排序了，说明这个数组是无序的，将flag置为1，下一次循环又将flag置为0，我们在下面判断，如果flag为0的话，就说明这个数组没有元素交换过，也就是说这个数组是有序的，既然它是有序的，我们就马上结束这个程序，这样优化我们的冒泡排序就不会每次进入它的时间复杂度都是O(N^2）了，如果这个数组是有序的，那么只会遍历一遍数组就结束程序，此时它的速度是0(N)。

2.6 快速排序

    快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

2.6 1 快速排序思路

快速排序（Quick Sort）是一种高效的排序算法，它使用分治策略来对一个数组进行排序。以下是快速排序的基本思路：

1. 选择基准：
   从数组中选择一个元素作为基准（key）。这个基准可以是数组中的第一个元素、最后一个元素、中间元素，或者通过某种方式随机选择的元素。

2. 分区：
   重新排列数组，使得所有小于基准的元素都位于基准的左侧，所有大于基准的元素都位于基准的右侧。这个操作称为分区（partition）。

3. 递归排序：
   对基准左侧和右侧的子数组分别进行快速排序。这是一个递归的过程，直到子数组的大小为零或一（此时子数组已经是有序的）。

4. 合并：
   由于快速排序是原地排序，且通过递归已经保证了每个子数组的有序性，所以最终整个数组也会是有序的，不需要额外的合并步骤。

详细步骤

1. 初始化：

   • 设定数组的起始位置 left和结束位置 right。

2. 选择基准：

   • 选择数组中的一个元素作为基准，通常选择 array[right]（也可以选择其他元素）。

3. 分区：

   • 初始化一个指针 i，使其指向数组的起始位置 low。
   • 遍历数组，从 left 到 right-1：
     • 如果 array[i] <= key，则继续向右移动 i。
     • 如果 array[i] > key，则交换 array[i] 和 array[righth-1]（或者任何一个大于key 的未处理元素的位置），并将 right-1 向左移动一位（因为该位置已经处理过）。
   • 最后，将基准元素key 放到正确的位置上，即 array[i] 和 array[right] 之间（通常是通过交换 array[i] 和 array[right] 来完成）。

4. 递归排序：

   • 对基准左侧的子数组（left到 i-1）进行快速排序。
   • 对基准右侧的子数组（i+1 到 right）进行快速排序。

5. 结束条件：

   • 当子数组的大小为零或一时，递归结束，数组已经有序。

2.6 2 快速排序递归实现 

  到现在为止，我们已经了解了快速排序的大致思路，先来看递归实现的快速排序：

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
int GetMiddle(int* a, int left, int right)
{int mid = left + right + 1;if (a[left] < a[mid]){if (a[right] > a[mid]){return mid;}else if (a[right] > a[left]){return right;}else{return left;}}else //a[left]>a[mid]{if (a[right] > a[left]){return left;}else if (a[right] > a[mid]){return right;}else{return mid;}}
}void QuickSort(int* a, int left, int right)
{if (left >= right){return;}
//当left大于或等于right时，说明数组已经有序if ((left + right + 1) < 10){InsertSort(a + left, left + right + 1);
//假设快排递归将被排序数组分散成了
//一棵二叉树，我们知道二叉树的最后一层
//占了这棵树的大半结点，当左右加起来
//的数据少于10时，我们可以使用
//插入排序提高它的效率}else{//三数取中int mid = GetMiddle(a, left, right);Swap(&a[left], &a[mid]);int keyi = left;int begin = left, end = right;while (begin < end){while (begin < end && a[end] >= a[keyi]){end--;}while (begin < end && a[begin] <= a[keyi]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);keyi = begin;QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}
}

使用一组无序的数来测试一下：

int a[] = { 3,5,8,6,9,7,4,1,2,0,10 };

注意：此程序中的插入排序和三数取中算法都是为了优化快速排序，使它拥有更好的效率，快速排序的核心逻辑代码为：

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void QuickSort(int* a, int left, int right)
{if (left >= right){return;}//当left大于或等于right时，说明数组已经有序int keyi = left;int begin = left, end = right;while (begin < end){while (begin < end && a[end] >= a[keyi]){end--;}while (begin < end && a[begin] <= a[keyi]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);keyi = begin;QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}

2.6 3快速排序非递归：

  看到这里，小伙伴们不禁疑惑：我们既然可以使用递归实现快速排序，为什么还要使用非递归实现呢？

快排非递归的优势

快速排序非递归实现的重要性主要体现在以下几个方面：

1. 避免递归调用开销：递归实现虽然直观易懂，但在一些编程语言中，递归调用会引入额外的函数调用栈的使用和维护开销。非递归实现通过显式地使用栈来管理状态，可以有效避免这些开销，从而提高性能。

2. 防止栈溢出：在极端情况下，递归实现可能导致栈溢出，尤其是在处理大规模数据时。非递归实现使用显式的数据结构（如栈）来管理状态，不依赖于系统的调用栈，从而避免了栈溢出的风险。

3. 降低空间复杂度：递归实现可能需要更多的内存空间，因为每个递归调用都需要在内存中保留一些信息。非递归实现通常使用更少的内存，只需维护一些必要的状态信息，有助于减少内存使用。

4. 提升性能：在某些编程语言和环境中，递归调用的性能可能不如循环，因为每个递归调用都需要函数调用的开销。非递归实现可以更好地与一些编译器和优化器协同工作，从而提高性能。

5. 便于优化：非递归实现更容易进行一些优化，例如通过使用迭代而不是递归的方式来访问数组，以更好地利用CPU缓存。这种优化可以进一步提升算法的执行效率。

6. 适应特定场景：在一些对递归深度有限制的环境（如嵌入式系统）中，非递归实现是必须的，以确保算法能够正常运行。

 非递归思路

快速排序的非递归思路主要是通过手动管理一个栈来模拟递归过程中的函数调用栈，从而实现对数组的排序。以下是快速排序非递归思路的详细步骤：

1. 初始化栈

• 创建一个空栈，用于保存接下来需要排序的子数组的边界。这个栈可以是任意类型的栈结构，但通常使用整型栈来保存子数组的起始索引（left）和结束索引（right）。

2. 将整个数组的起始和结束索引入栈

• 这一步相当于递归排序中的初始调用。将数组的起始索引（left）和结束索引（right）作为一对入栈，表示接下来需要处理整个数组。

3. 循环处理栈中的子数组边界

• 不断从栈中弹出子数组的边界索引（一对），然后对这个子数组进行快速排序的单趟排序。

4. 单趟排序

• 在单趟排序中，首先选择一个元素作为基准（pivot）。基准的选择可以是子数组的第一个元素，也可以通过其他策略（如三数取中法）来选择。
• 进行分区操作，将子数组划分为比基准小的左侧部分和比基准大的右侧部分，并确定基准元素的最终位置。

5. 处理分区后的子数组

• 分区操作完成后，基准元素左侧的子数组（如果存在）和右侧的子数组（如果存在）可能还需要继续排序。
• 如果左侧子数组有多个元素，则将其起始和结束索引作为一对入栈。
• 如果右侧子数组有多个元素，也将其起始和结束索引作为一对入栈。

6. 重复步骤3和步骤5

• 继续迭代该过程，直到栈为空。此时，所有的子数组都已经被正确排序，整个数组也就完成了排序。

注意事项

• 在单趟排序中，分区操作是关键步骤，它决定了基准元素的最终位置，并将数组划分为两个子数组。
• 栈的使用是非递归快速排序的核心，它模拟了递归调用栈的功能，允许我们手动管理子数组的排序顺序。
• 非递归快速排序的性能与递归快速排序相近，但在某些情况下（如递归深度过大导致栈溢出）可能更加稳定可靠。

总结：通过以上步骤，我们可以实现快速排序的非递归版本，从而在处理大规模数据时避免递归调用栈的限制。

由于c语言没有STL，我们使用c＋＋来实现：

int GetMiddle(int* a, int left, int right)
{int mid = left + right + 1;if (a[left] < a[mid]){if (a[right] > a[mid]){return mid;}else if (a[right] > a[left]){return right;}else{return left;}}else //a[left]>a[mid]{if (a[right] > a[left]){return left;}else if (a[right] > a[mid]){return right;}else{return mid;}}
}
int PartSort1(int* a, int left, int right)
{// 三数取中int midi = GetMiddle(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int begin = left, end = right;while (begin < end){// 右边找小while (begin < end && a[end] >= a[keyi]){--end;}// 左边找大while (begin < end && a[begin] <= a[keyi]){++begin;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);return begin;
}//非递归
void QuickSortNonR(int* a, int left, int right)
{stack<int> st;st.push(right);st.push(left);while (!st.empty()){int begin = st.top();st.pop();int end = st.top();st.pop();int keyi = PartSort1(a, begin, end);if (keyi+1 < end){st.push(end);st.push(keyi+1);}if (begin < keyi - 1){st.push(keyi - 1);st.push(begin);}}
}

我们来测试一下：

可以看到我们的快排非递归也是成功地实现了。

快速排序的特性总结：

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(logN)
4. 稳定性：不稳定 

总结：快速排序是一种非常高效的排序算法，尤其适用于大部分元素已经有序的情况。通过合理选择基准和优化递归过程，可以进一步提高其性能。

2.7 归并排序

基本思想：

   归并排序（Merge Sort）是一种分治策略的排序算法，其基本思想是将一个序列分为两个较小的子序列，直到子序列的大小为1，然后将已排序的子序列合并成一个大的有序序列。以下是归并排序的完整思路：

一、算法步骤

1. 分割：

   • 将待排序的数组分成两半，如果数组长度为奇数，则其中一部分会比另一部分多一个元素。
   • 对这两部分数组继续递归地进行分割，直到子数组的长度为1，此时可以认为每个子数组都是有序的（因为只有一个元素）。

2. 治理（解决）：

   • 这一步在归并排序中实际上是通过分割步骤隐含完成的。当子数组的长度为1时，它们自然就是有序的，无需进一步处理。

3. 合并：

   • 将相邻的有序子数组合并成一个有序数组，直到合并为1个完整的数组。
   • 合并过程中，通过比较两个子数组的元素，按大小顺序依次放入新的数组中，从而实现排序。

二、具体实现

1. 申请空间：

   • 创建一个临时数组，用于存放合并后的子数组。

2. 设定指针：

   • 在两个待合并的子数组上分别设置指针，初始时都指向子数组的起始位置。

3. 比较合并：

   • 比较两个指针所指向的元素，将较小的元素放入临时数组，并移动该指针。
   • 重复此过程，直到某个子数组的所有元素都被复制到临时数组中。
   • 将另一个子数组中剩余的元素（如果有的话）直接复制到临时数组的末尾。

4. 复制回原数组：

   • 将临时数组中的元素复制回原数组，以替换原来的子数组。

归并排序递归实现：

void _MergeSort(int* a, int* tmp,int begin,int end)
{if (begin >= end){return;}int mid = (begin + end) / 2;_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid+1, end);int begin1 = begin, end1 = mid;int begin2 = mid+1, end2 = end;int i = begin;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++];}memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));}
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");}_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp = NULL;}

此程序涉及在堆上申请资源，所以我们分两个接口实现。

归并排序非递归实现： 

//归并排序非递归
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * (n+1));if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap <= n){for (int j = 0; j <= n;j+=gap*2){int begin1 = j, end1 = j + gap - 1;int begin2 = j + gap, end2 = j + gap * 2 - 1;if (begin2 > n ){break;}if (end2 > n){end2 = n;}int i = j;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++];}memcpy(a + j, tmp + j, sizeof(int) * (end2 - j+1));}gap *= 2;}free(tmp);tmp == NULL;}

给一组无序数，我们来测试一下：

int a[] = { 3,5,7,1,2,0,9,10,4,8,11 };

 

可以看到没有什么问题。

 

三、性能分析

• 时间复杂度：归并排序的时间复杂度为O(n log n)，其中n是数组的长度。在每一层递归中，合并操作的时间复杂度为O(n)，而递归的层数为log n，因此总的时间复杂度为O(n log n)。
• 空间复杂度：归并排序的空间复杂度也是O(n)，因为需要额外的空间来创建临时数组。
• 稳定性：归并排序是稳定的排序算法，即相等的元素在排序后的顺序与它们在原数组中的顺序相同。

总结：归并排序因其稳定的排序特性和较好的平均性能，在实际应用中非常广泛。特别是在数据量较大时，归并排序能够展现出其高效的排序能力。 

2.8 计数排序

计数排序概念：

     计数排序（Counting Sort）是一种非基于比较的排序算法，由Harold H. Seward在1954年提出。它适用于待排序元素为整数且范围较小的情况。计数排序的基本思想是统计每个元素的出现次数，然后利用这些信息将原始序列重新组合成有序序列。

一、计数排序的原理与步骤

计数排序的工作原理主要包括以下几个步骤：

1. 统计元素出现次数：

   • 遍历待排序的数组，统计每个元素出现的次数。这通常通过创建一个辅助数组（计数数组）来实现，该数组的长度等于待排序数组中元素的最大值加1（如果元素是非负整数）。

2. 前缀和操作：

   • 对计数数组进行前缀和操作，使得每个元素的值变为小于等于该元素的值的元素总数。这样，计数数组的每个位置就对应了原数组中元素在排序后数组中的位置。

3. 重建有序数组：

   • 遍历待排序数组，根据计数数组的信息，将元素放回其在有序数组中的正确位置。同时，更新计数数组中对应元素的值，以确保相同元素的相对顺序不变。

二、计数排序的示例

假设我们有一个待排序的数组arr = [4, 2, 2, 8, 3, 3, 1]，我们可以按照计数排序的步骤对其进行排序：

1. 统计元素出现次数：

   • 遍历数组arr，得到计数数组count = [0, 1, 2, 2, 2, 0, 1, 1]（假设数组中的元素都是非负整数，且最大值不超过7）。

2. 前缀和操作：

   • 对计数数组进行前缀和操作，得到count = [0, 1, 3, 5, 7, 7, 7, 8]。

3. 重建有序数组：

   • 遍历数组arr，根据计数数组的信息将元素放回有序数组中的正确位置。排序后的数组为sorted_arr = [1, 2, 2, 3, 3, 4, 8]。

 计数排序代码实现：

void CountSort(int* a, int n)
{int max = a[0], min = a[0];for (int i = 0; i < n; i++){if (a[i] > max){max = a[i];}if (a[i] < min){min = a[i];}}int range = max - min + 1;int* count = (int*)calloc(range, sizeof(int));if (count == NULL){perror("calloc fail");}for (int i = 0; i <n; i++){count[a[i] - min]++;}int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}}

给一组无序数测试一下：

int a[] = { 2,4,76,87654,98,12,76,454,23,98 };

 

    虽然我们的排序成功了，但是这个程序内部开辟了非常多的空间，所以当一组数的最大值和最小值相差太多时，不建议使用计数排序。

三、注意事项

• 在使用计数排序时，需要确保待排序数组中的元素都是非负整数或可映射到非负整数范围内。如果待排序的元素不满足这个要求，就需要对其进行映射转换。
• 当待排序元素的范围非常大时，计数排序可能会消耗大量的内存空间，因此在实际应用中需要注意这一点。

四、计数排序的特点

1. 时间复杂度：

   • 计数排序的时间复杂度为O(n+k)，其中n是待排序数组的长度，k是待排序数组中元素的范围。当k不是很大时，计数排序的时间复杂度接近线性，快于任何基于比较的排序算法（如快速排序、归并排序等，它们的时间复杂度在理论上的下限是O(n log n)）。

2. 空间复杂度：

   • 计数排序的空间复杂度为O(k)，其中k是待排序数组中元素的范围。因此，计数排序是一种牺牲空间换取时间的排序算法。

3. 稳定性：

   • 计数排序是稳定的排序算法，即相等的元素在排序后的序列中保持它们原有的先后顺序。

4. 适用场景：

   • 计数排序特别适用于整数排序，特别是当整数的范围不是很大时。对于非整数类型的数据或整数范围非常大的情况，计数排序可能不适用或效率较低。

 本章完。