什么网站可以在图片上做超链接,wordpress不同侧边栏,四川手机响应式网站建设推荐,制作网站免费目录
一、排序的概念
二、插入排序
1、直接插入排序
直接插入排序的特性总结#xff1a;
2、希尔排序
希尔排序的特性总结#xff1a; 三、选择排序
1、直接选择排序
时间复杂度
2、堆排序—排升序(建大堆)
向下调整函数
堆排序函数
代码完整版#xff1a; …目录
一、排序的概念
二、插入排序
1、直接插入排序
直接插入排序的特性总结
2、希尔排序
希尔排序的特性总结 三、选择排序
1、直接选择排序
时间复杂度
2、堆排序—排升序(建大堆)
向下调整函数
堆排序函数
代码完整版 头文件 函数文件 测试文件 一、排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 二、插入排序 比如在实际中我们玩扑克牌时就用了插入排序的思想 1、直接插入排序 直接插入排序是一种简单的排序算法它的基本思想是将一个记录插入到已经排序好的有序表中从而得到一个新的、记录数增加1的有序表。这个算法适用于少量数据的排序是稳定的排序方法即相等的元素的顺序不会改变。 直接插入排序的算法过程如下 从第一个元素开始该元素可以认为已经被排序取出下一个元素在已经排序的元素序列中从后向前扫描如果该元素已排序大于新元素将该元素移到下一位置重复步骤3直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5。 如果我们将这个过程比作扑克牌的排序每次我们都是从牌堆中拿出一张牌然后将它插入到左手中正确的位置最终左手中的牌都是排序好的。 我们来看一下代码的运行过程
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i) {int end i;int tmp a[i 1];while (end 0) {if (a[end] tmp) {a[end 1] a[end];end--;}else {break;}}a[end 1] tmp;}
}
函数参数指针a接收数组n接收数组元素个数。首先外层循环从第一个元素开始遍历到倒数第二个元素因为在内层循环中需要比较当前元素和前一个元素的大小所以最后一个元素不需要再比较。在外层循环中我们将当前元素的下一个元素作为待插入元素将当前元素的下标保存在变量end中这个变量表示当前元素在已排序部分中的位置。接下来while循环中我们在已排序部分从后往前遍历比较当前元素和已排序部分中的元素大小如果当前元素小于已排序部分中的元素则将已排序部分中的元素后移一位直到找到当前元素的正确位置。最后我们将待插入元素插入到正确的位置即end1的位置。内层循环结束后当前元素已经被插入到了正确的位置我们继续外层循环处理下一个元素直到所有元素都被插入到正确的位置。
直接插入排序的特性总结 1. 元素集合越接近有序直接插入排序算法的时间效率越高 2. 时间复杂度O(N^2) 3. 空间复杂度O(1)它是一种稳定的排序算法 4. 稳定性稳定 2、希尔排序 希尔排序Shell Sort是一种改进的插入排序算法它的基本思想是将待排序的序列分成若干个子序列对每个子序列进行插入排序然后再将整个序列进行一次插入排序。通过这种方式可以使得序列中较小的元素尽可能地快速地移动到前面从而减少了插入排序的比较次数和移动次数提高了排序的效率。 希尔排序的算法过程如下
选择一个增量序列t1t2…tk其中titjtk1按增量序列个数k对序列进行k趟排序每趟排序根据对应的增量ti将待排序列分割成若干长度为m的子序列分别对每个子序列进行插入排序将各个子序列中的排序结果合并成一个序列。
代码如下
void ShellSort(int* a, int n)
{//1、gap 1 预排序//2、gap 1 直接插入排序int gap n;while (gap 1) {gap gap / 3 1;// 1可以保证最后一次一定是1for (int i 0; i n - gap; i) {int end i;int tmp a[end gap];while (end 0) {if (a[end] tmp) {a[end gap] a[end];end - gap;}else {break;}}a[end gap] tmp;}}
}
首先我们选择一个增量gapn然后将序列分成若干个子序列对每个子序列进行插入排序。在这个实现中我们使用了一个while循环来计算增量gap每次将gap除以3并加1保证gap最小为1此时进行直接插入排序。在外层while循环中我们将序列分成若干个子序列每个子序列的长度为gap。然后我们对每个子序列进行插入排序将子序列中的元素插入到已排序部分的正确位置。 在内层循环中我们使用了一个变量end来表示当前元素的下标每次将end减去gap直到找到当前元素的正确位置。然后我们将待插入元素插入到正确的位置即endgap的位置。 内层循环结束后当前子序列已经排好序了我们继续外层while循环处理下一个子序列直到所有子序列都被排好序了。 以数组 a [9, 8, 7, 6, 5, 4, 3, 3, 2, 1, 0]长度 n 11为例演示排序过程 图中颜色相同的值为当前间距gap下的子序列从前往后依次比较每个子序列也就是相距 gap 个位置的值的大小。 希尔排序的特性总结 希尔排序是对直接插入排序的优化。 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。 希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些书中给出的希尔排序的时间复杂度都不固定但我们只需记住结论ON^ 1.3复杂的推导和计算过程不需要了解。 三、选择排序
1、直接选择排序 直接选择排序通过每一轮的比较找到最大值和最小值将最大值的节点跟右边交换最小值节点跟左边交换达到排升序的效果。 我们先看代码然后通过一个例子就能明白了。
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int maxi begin, mini begin;for (int i begin; i end; i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}Swap(a[begin], a[mini]);// 如果maxi和begin重叠修正一下即可if (begin maxi){maxi mini;}Swap(a[end], a[maxi]);begin;--end;}
}
代码中的变量begin和end分别表示当前未排序的元素范围的起始和结束位置。在while循环中每次从begin到end的范围内找到最大和最小的元素分别用maxi和mini记录它们的下标。然后将mini所指向的元素与begin所指向的元素交换位置将maxi所指向的元素与end所指向的元素交换位置。如果maxi和begin重叠说明mini所指向的元素是当前未排序元素中最大的需要将maxi更新为mini。最后begin指针向后移动一位end指针向前移动一位继续进行下一轮排序。 我们来用一个简单的例子演示一下这个选择排序算法的过程。 假设我们有一个数组a它的元素为[5, 3, 8, 6, 4, 2]我们要对它进行排序。 首先begin指向第一个元素end指向最后一个元素 begin 0
end 5 接下来我们进入主循环因为begin小于end所以我们需要继续排序。在第一轮排序中我们需要找到未排序部分的最大值和最小值。 首先我们将maxi和mini都初始化为begin也就是第一个元素的索引。然后我们遍历未排序部分的元素找到最大值和最小值的索引。在这个例子中最大值的索引是2最小值的索引是5。 maxi 2
mini 5 接下来我们将未排序部分的最小值交换到开始位置将未排序部分的最大值交换到结束位置。这时数组的状态变为[2, 3, 4, 6, 8, 5] 由于我们已经将当前范围的最大值和最小值放到了正确的位置所以我们将begin向后移动一位将end向前移动一位继续进行下一轮排序。此时begin指向第二个元素end指向倒数第二个元素 begin 1
end 4 在第二轮排序中我们需要找到未排序部分的最大值和最小值。这时最大值的索引是3最小值的索引是1。 maxi 3
mini 1 接下来我们将未排序部分的最小值交换到开始位置将未排序部分的最大值交换到结束位置。这时数组的状态变为[2, 3, 4, 5, 6, 8]所有元素都排序完成排序结束。 时间复杂度 每一轮比较都需要遍历数组查找最大最小值第一轮遍历N个数据第二轮是N-2个数据第三轮N-4 …遍历次数为NN-2N-4…1一个等差数列求和所以总的时间复杂度为O(N^2) 2、堆排序—排升序(建大堆)
向下调整函数
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n){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;}elsebreak;}
}
通过传入参数获取到当前的左子节点的位置。当child位置小于数组元素个数时进行判断。进入循环首先判断检查右子节点是否存在并且比左子节点的值大如果是将 child 更新为右子节点的索引以确保选择更小的子节点进行比较。比较选定的子节点的值与父节点的值如果子节点的值大于父节点的值就交换它们。更新parent为新的子节点位置更新child为新的左子节点位置然后继续比较和交换直到不再需要交换为止。如果当前子节点不大于当前父节点则停止循环。
堆排序函数
// 排升序
void HeapSort(int* a, int n)
{// 建大堆for (int i (n-1-1)/2; i 0; --i){AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
} 在HeapSort函数中第一个循环调用了AdjustDown函数将待排序数组构建成了一个大堆。但是这个大堆并不是完全有序的只是满足了大堆的性质即每个节点的值都大于或等于其左右子节点的值。因此需要进行第二个while循环将大堆中的元素依次取出交换堆顶元素和数组末尾元素并重新调整大堆直到整个数组有序。第二个while循环中将堆顶元素与数组末尾元素交换然后将剩余元素重新调整为大堆。这样每次交换后数组末尾的元素就是当前大堆中的大值而剩余元素仍然满足大堆的性质。重复以上步骤直到整个数组有序。
代码完整版 头文件
#includestdio.h
#includestdlib.h
#includestdbool.hvoid PrintArray(int* a, int n);
void InsertSort(int* a, int n);
void ShellSort(int* a, int n);
void SelectSort(int* a, int n);
void HeapSort(int* a, int n); 函数文件
#include sort.hvoid PrintArray(int* a, int n)
{for (int i 0; i n; i) {printf(%d , a[i]);}printf(\n);
}void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i) {int end i;int tmp a[i 1];while (end 0) {if (a[end] tmp) {a[end 1] a[end];end--;}else {break;}}a[end 1] tmp;}
}void ShellSort(int* a, int n)
{//1、gap 1 预排序//2、gap 1 直接插入排序int gap n;while (gap 1) {gap gap / 3 1;// 1可以保证最后一次一定是1for (int i 0; i n - gap; i) {int end i;int tmp a[end gap];while (end 0) {if (a[end] tmp) {a[end gap] a[end];end - gap;}else {break;}}a[end gap] tmp;}}
}void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int maxi begin, mini begin;for (int i begin; i end; i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}Swap(a[begin], a[mini]);// 如果maxi和begin重叠修正一下即可if (begin maxi){maxi mini;}Swap(a[end], a[maxi]);begin;--end;}
}void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n) {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 HeapSort(int* a, int n)
{for (int i (n - 1 - 1) / 2; i 0; --i) {AdjustDown(a, n, i);}int end n - 1;while (end 0) {Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}测试文件
#includeSort.h
#includetime.hvoid TestInsertSort()
{//int a[] { 4,7,1,9,3,4,5,8,3,2 };int a[] { 4,7,1,9,3,6,5,8,3,2,0 };PrintArray(a, sizeof(a) / sizeof(int));InsertSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestSelectSort()
{//int a[] { 4,7,1,9,3,6,5,8,3,2,0 };int a[] { 9,7,1,3,3,0,5,8,3,2,3 };PrintArray(a, sizeof(a) / sizeof(int));SelectSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestHeapSort()
{int a[] { 4,7,1,9,3,6,5,8,3,2,0 };PrintArray(a, sizeof(a) / sizeof(int));HeapSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestOP()
{srand(time(0));const int N 1000000;//运行时间较长可自行更改大小int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);int* a3 (int*)malloc(sizeof(int) * N);int* a4 (int*)malloc(sizeof(int) * N);int* a5 (int*)malloc(sizeof(int) * N);int* a6 (int*)malloc(sizeof(int) * N);int* a7 (int*)malloc(sizeof(int) * N);for (int i 0; i N; i){a1[i] rand();a2[i] a1[i];a3[i] a1[i];a4[i] a1[i];a5[i] a1[i];a6[i] a1[i];a7[i] a1[i];}int begin1 clock();InsertSort(a1, N);int end1 clock();int begin2 clock();ShellSort(a2, N);int end2 clock();int begin3 clock();SelectSort(a3, N);int end3 clock();int begin4 clock();HeapSort(a4, N);int end4 clock();printf(InsertSort:%d\n, end1 - begin1);printf(ShellSort:%d\n, end2 - begin2);printf(SelcetSort:%d\n, end3 - begin3);printf(HeapSort:%d\n, end4 - begin4);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}int main()
{//TestInsertSort();//TestShellSort();//TestSelectSort();//TestHeapSort();TestOP();return 0;
}
