网站 运营 外包 每个月多少钱,高校官方网站建设,wordpress安装md,深圳网站建设电话目录
一、排序的概念
二、插入排序
直接插入排序
希尔排序
三、选择排序
选择排序
堆排序
四、交换排序
冒泡排序
快速排序
递归实现 非递归实现
五、归并排序
递归
非递归
六、非比较排序#xff08;计数排序#xff09;
七、其他排序
基数排序
桶排序
八…目录
一、排序的概念
二、插入排序
直接插入排序
希尔排序
三、选择排序
选择排序
堆排序
四、交换排序
冒泡排序
快速排序
递归实现 非递归实现
五、归并排序
递归
非递归
六、非比较排序计数排序
七、其他排序
基数排序
桶排序
八、总结 一、排序的概念
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。
稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排 序算法是稳定的否则称为不稳定的。
内部排序数据元素全部放在内存中的排序。
外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
常见的排序算法 二、插入排序 基本思想直接插入排序是一种简单的插入排序法 其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为 止得到一个新的有序序列 。 实际中我们玩扑克牌时就用了插入排序的思想 直接插入排序
当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移 代码实现
// 插入排序
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int endi;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
} 直接插入排序的特性总结 1. 元素集合越接近有序直接插入排序算法的时间效率越高 2. 时间复杂度O(N^2) 3. 空间复杂度O(1)它是一种稳定的排序算法 4. 稳定性稳定 希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个 组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。 代码实现
// 希尔排序
void ShellSort(int* a, int n)
{int get n;while (get 1){get get / 3 1;for (int i 0; i n - get; i){int end i;int tmp a[end get];while (end 0){if (tmp a[end]){a[end get] a[end];end - get;}else{break;}}a[endget] tmp;}}
} 希尔排序的特性总结 1. 希尔排序是对直接插入排序的优化。 2. 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。 3. 希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的 希尔排序的时间复杂度都不固定 《数据结构(C语言版)》--- 严蔚敏 《数据结构-用面相对象方法与C描述》--- 殷人昆 4. 稳定性不稳定 三、选择排序
基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的 数据元素排完 。
选择排序
直接选择排序: 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素 若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换 在剩余的array[i]--array[n-2]array[i1]--array[n-1]集合中重复上述步骤直到集合剩余1个元素 代码实现
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
// 选择排序
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int max begin, min begin;for (int i begin 1; i end; i){if (a[i]a[max]){max i;}if (a[i] a[min]){min i;}}Swap(a[begin], a[min]);if (max begin)max min;Swap(a[end], a[max]);begin;end--;}
} 直接选择排序的特性总结 1. 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用 2. 时间复杂度O(N^2) 3. 空间复杂度O(1) 4. 稳定性不稳定 堆排序
堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是 通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。 代码实现
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
// 堆排序
void AdjustDwon(int* a, int n, int root)
{int child root * 2 1;while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[root]){Swap(a[root], a[child]);root child;child root * 2 1;}else{break;}}
}
void HeapSort(int* a, int n)
{for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDwon(a, n, i);}int end n - 1;while (end0){Swap(a[0], a[end]);AdjustDwon(a, end, 0);end--;}
}
关于TOP--K问题在之前的文章讲过TOP-K问题 直接选择排序的特性总结 1. 堆排序使用堆来选数效率就高了很多。 2. 时间复杂度O(N*logN) 3. 空间复杂度O(1) 4. 稳定性不稳定 四、交换排序
基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排 序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
冒泡排序 代码实现
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
// 冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i){for (int j 0; j n - 1 - i; j){if (a[j] a[j 1]){Swap((a[j]),(a[j1]));}}}
} 冒泡排序的特性总结 1. 冒泡排序是一种非常容易理解的排序 2. 时间复杂度O(N^2) 3. 空间复杂度O(1) 4. 稳定性稳定 快速排序
递归实现
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中 的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右 子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
快速排序递归实现的主框架发现与二叉树前序遍历规则非常像在写递归框架时可想想二叉树前序遍历规则即可快速写出来后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
常见快排方式有
1. hoare版本 思路 1. 选择一个基准元素。 2. 定义两个指针一个从数组开头left一个从数组末尾right。 3. 从右向左找第一个小于基准的元素从左向右找第一个大于基准的元素然后交换这两个元素使得左边小于等于基准的元素都在基准左侧右边大于等于基准的元素都在基准右侧。 4. 重复这个过程直到 left 和 right 指针相遇此时基准元素的位置就确定了该位置左侧都是小于等于它的右侧都是大于等于它的。 5. 对基准元素左右两侧的子数组分别重复上述过程进行排序。 通过不断地划分和对子部分排序最终实现整个数组的排序。 代码实现
void QuickSort(int* a, int left, int right)
{if (left right){return;}int key left;int begin left;int end right;while (beginend){while (begin end a[key]a[end]){end--;}while (begin end a[key]a[begin]){begin;}Swap(a[end],a[begin]);}Swap(a[key], a[begin]);key begin;QuickSort(a, left, key - 1);QuickSort(a, key 1, right);
}
2. 挖坑法 思路 1. 选择基准元素通常选择数组的第一个元素或最后一个元素作为基准。 2. 初始化左右指针将左右指针分别指向数组的第一个元素和最后一个元素。 3. 挖坑将基准元素保存到一个临时变量中此时基准元素的位置就形成了一个“坑”。 4. 从右向左移动右指针找到第一个小于基准的元素将其填入“坑”中同时右指针原来的位置形成了一个新的“坑”。 5. 从左向右移动左指针找到第一个大于基准的元素将其填入新的“坑”中同时左指针原来的位置形成了一个新的“坑”。 6. 重复步骤 4 和 5直到左指针和右指针相遇此时将基准元素填入最后的“坑”中完成一次划分。 7. 对基准元素左边和右边的子数组分别重复步骤 1 到 6进行递归排序。 通过不断地划分和递归最终可以将整个数组排序。 代码实现
int PartSort(int* a, int begin, int end)
{//begin是坑int key a[begin];while (begin end){while (begin end a[end] key)--end;// end给begin这个坑end就变成了新的坑。a[begin] a[end];while (begin end a[begin] key)begin;// end给begin这个坑begin就变成了新的坑。a[end] a[begin];}a[begin] key;return begin;
}void QuickSort(int* a, int left, int right)
{if (left right){return;}int key PartSort(a,left,right);QuickSort(a, left, key - 1);QuickSort(a, key 1, right);
}
3. 前后指针版本 思路 1. 选择一个基准元素。 2. 初始化两个指针前指针 prev 从数组起始位置开始后指针 cur 也从起始位置开始。 3. cur 指针向后移动遇到小于等于基准元素的就停下来。 4. 此时 prev 指针向前移动一步如果 prev 和 cur 不相等然后交换 prev 所指向的元素和 cur 所指向的元素。 5. 继续重复步骤 3 和 4直到 cur 遍历完整个数组。 6. 交换基准元素和 prev 指针最终停留位置的元素这样就完成了一次划分基准元素左边都是小于等于它的右边都是大于等于它的。 7. 对基准元素左右两侧的子数组分别重复上述过程进行递归排序。 通过这样不断地划分和递归最终实现数组的排序。 代码实现
// 快速排序前后指针法
int PartSort(int* a, int left, int right)
{int key left;int prev left;int cur left 1;while (cur right){if (a[cur] a[key] prev ! cur)Swap(a[prev], a[cur]);cur;}Swap(a[prev], a[key]);return prev;
}
void QuickSort(int* a, int left, int right)
{if (left right){return;}int key PartSort(a,left,right);QuickSort(a, left, key - 1);QuickSort(a, key 1, right);
}
快速排序优化 三数取中法选key 1. 从待排序序列中选择三个元素可以是第一个元素、中间元素和最后一个元素或者其他固定位置的元素。 2. 对这三个元素进行比较找出中间大小的元素。 3. 将中间大小的元素作为基准元素。 通过使用三数取中法选择基准元素可以减少快速排序在最坏情况下的时间复杂度提高排序的效率。这种方法在处理大部分数据时都能取得较好的效果但在某些特殊情况下可能仍然需要进一步的优化或选择其他合适的排序算法。 小区间优化 快速排序的小区间优化是指在快速排序的递归过程中当待排序的区间长度较小时不再继续进行递归调用而是采用其他更高效的排序算法对小区间进行排序。常见的小区间优化方法包括以下几种 • 插入排序当区间长度小于某个阈值时使用插入排序算法对小区间进行排序。插入排序在小型数据集上的性能较好能够提高排序效率。 • 选择排序与插入排序类似当区间长度较小时选择排序也是一种简单有效的排序算法。 • 直接排序对于非常小的区间可以直接使用冒泡排序或其他简单的排序算法进行排序。 通过采用小区间优化可以减少递归调用的次数降低时间复杂度特别是在处理大规模数据时能够提高快速排序的整体性能。 通过采用小区间优化可以减少递归调用的次数降低时间复杂度特别是在处理大规模数据时能够提高快速排序的整体性能。 代码实现
int GetMidi(int* a, int left, int right) //三数取中
{int midi (left right)/2;if (a[left] a[midi]){if (a[midi] a[right])return midi;else if (a[left] a[right])return right;elsereturn left;}else//a[left]a[midi]{if (a[midi] a[right])return midi;else if (a[left] a[right])return left;elsereturn right;}}//快速排序递归实现
void QuickSort(int* a, int left, int right)
{if (left right){return;}if (( right- left 1) 10) //小区间优化 最后10个数 走插入排序{InsertSort(a left, right - left 1);//插入排序}else{int midi GetMidi(a, left, right); //三数取中 Swap(a[left], a[midi]);int key left;int begin left;int end right;while (begin end){while (begin end a[end] a[key]){end--;}while (begin end a[begin] a[key]){begin;}Swap(a[end], a[begin]);}Swap(a[key], a[begin]);key begin;QuickSort(a, left, key - 1);QuickSort(a, key 1, right);}
} 非递归实现 思路 1. 初始化栈创建一个栈来模拟递归过程。 2. 选择基准并划分先选择一个基准元素对当前区间进行划分得到左右两个子区间。 3. 入栈将左右子区间的边界信息起始位置和结束位置分别入栈。 4. 循环处理不断从栈中取出区间信息对取出的区间重复进行划分和入栈操作直到栈为空。 在这个过程中通过栈来保存未处理完的子区间从而以非递归的方式实现了原本递归的逻辑。这样可以避免递归调用带来的栈空间开销过大等问题。 代码实现
栈的代码
void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-top 0;pst-capacity 0;
}
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-capacity pst-top 0;
}
void STPush(ST* pst, STDataType x)
{if (pst-top pst-capacity){int newCapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, newCapacity * sizeof(STDataType));if (tmp NULL){perror(realloc err);return;}pst-a tmp;pst-capacity newCapacity;}pst-a[pst-top] x;pst-top;
}
void STPop(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst-top--;
}
STDataType STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst-a[pst-top - 1];
}
bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;
}
快排非递归代码
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(st);STPush(st, right);STPush(st, left);while (!STEmpty(st)){int begin STTop(st);STPop(st);int end STTop(st);STPop(st);int keyi PartSort1(a, begin, end);if (keyi 1 end){STPush(st, end);STPush(st, keyi 1);}if (begin keyi - 1){STPush(st, keyi - 1);STPush(st, begin);}}} 快速排序的特性总结 1. 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序 2. 时间复杂度O(N*logN) 3. 空间复杂度O(logN) 4. 稳定性不稳定 五、归并排序
基本思想 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有 序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 递归 1. 将数组不断地分成两半直到每个部分只剩下一个元素或为空。 2. 对分成的左右两部分分别进行排序。 3. 将已排序的左右两部分合并成一个有序的整体。 在递归过程中先找到中间位置将数组一分为二然后对左右两部分递归调用归并排序函数进行排序。在合并阶段创建一个辅助数组通过比较左右两部分的元素依次将较小的元素放入辅助数组最后将辅助数组的内容复制回原数组对应的位置从而完成一次合并经过多次这样的递归和合并操作最终使整个数组有序。 代码实现
void _MergeSort(int* a,int* tmp,int begin,int end)
{if (begin end){return;}int mini (begin end) / 2;_MergeSort(a, tmp, begin, mini);_MergeSort(a, tmp, mini 1, end);int i begin;int begin1 begin, end1 mini;int begin2 mini 1, end2 end;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[i] a[begin2];elsetmp[i] a[begin1];}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 err);return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp NULL;
}
非递归 1. 首先从较小的子序列长度开始比如初始子序列长度为 1。 2. 不断将相邻的具有相同长度的子序列两两合并得到新的长度翻倍的子序列。 3. 在合并过程中对两个子序列进行比较和排序操作将它们合并成一个有序的子序列。 4. 逐步增加子序列的长度重复进行合并操作直到整个数组被合并完成为止。 具体实现时通过循环逐步扩大子序列的长度每次循环中对所有满足当前子序列长度的相邻区间进行合并操作。这样就可以在不使用递归的情况下实现归并排序的过程。 代码实现
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc err);}int gap 1;while(gap n){for (int i 0; i n; i 2 * gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;if (begin2 n)break;if (end2 n)end2 n - 1;int j i;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[j] a[begin2];elsetmp[j] a[begin1];}while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));}gap * 2;}free(tmp);tmp NULL;
} 归并排序的特性总结 1. 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。 2. 时间复杂度O(N*logN) 3. 空间复杂度O(N) 4. 稳定性稳定 六、非比较排序计数排序 思想计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 操作步骤 1. 统计相同元素出现次数 2. 根据统计的结果将序列回收到原来的序列中 代码实现
// 计数排序
void CountSort(int* a, int n)
{int min a[0], max a[0];for (int i 1; i n; i){if (a[i] max)max a[i];if (a[i] min)min a[i];}int ragn max - min 1;int* count calloc(ragn, sizeof(int));if (count NULL){perror(calloc err);return;}for (int i 0; i n; i){count[a[i]-min];}int j 0;for (int i 0; i ragn; i){while (count[i]--){a[j] i min;}}
} 计数排序的特性总结 1. 计数排序在数据范围集中时效率很高但是适用范围及场景有限。 2. 时间复杂度O(MAX(N,范围)) 3. 空间复杂度O(范围) 4. 稳定性稳定 七、其他排序
基数排序 1. 确定基数通常根据待排序元素的特征如数字的个位、十位、百位等确定一个基数。 2. 按位分配和收集从最低位如个位开始将所有元素按照当前位的值分配到不同的“桶”中然后按桶的顺序依次取出元素这就完成了当前位的排序。接着对下一位重复这样的操作依次向高位推进。 3. 重复过程不断重复上述步骤对每一位进行排序和收集直到对最高位完成操作此时整个数组就实现了排序。 基数排序适用于特殊情况尤其是当元素的每一位都比较容易提取和处理时它可以高效地对大量数据进行排序。 代码实现
// 获取数字指定位上的数字
int getDigit(int num, int digit) {int divisor 1;for (int i 0; i digit - 1; i) {divisor * 10;}return (num / divisor) % 10;
}// 对指定基数进行计数排序
void countingSort(int arr[], int n, int exp) {int output[n];int count[10] {0};for (int i 0; i n; i) {count[getDigit(arr[i], exp)];}for (int i 1; i 10; i) {count[i] count[i - 1];}for (int i n - 1; i 0; i--) {output[count[getDigit(arr[i], exp)] - 1] arr[i];count[getDigit(arr[i], exp)]--;}for (int i 0; i n; i) {arr[i] output[i];}
}// 基数排序函数
void radixSort(int arr[], int n) {int max arr[0];for (int i 1; i n; i) {if (arr[i] max) {max arr[i];}}for (int exp 1; max / exp 0; exp * 10) {countingSort(arr, n, exp);}
}桶排序 1. 创建桶根据待排序数据的范围和特点创建若干个桶。 2. 数据分配将各个元素根据特定规则分配到相应的桶中。 3. 桶内排序对每个桶内的元素进行排序可以使用其他简单排序方法。 4. 依次取出按照桶的顺序依次取出所有桶中的元素得到有序序列。 桶排序的关键在于合理地划分桶以及高效地处理桶内数据。通常适用于数据分布比较均匀且容易划分桶的情况。它在一些特定场景下能高效地完成排序任务。 代码实现
#include stdio.h
#include stdlib.h// 对每个桶进行插入排序
void insertionSort(int bucket[], int bucketSize) {for (int i 1; i bucketSize; i) {int key bucket[i];int j i - 1;while (j 0 bucket[j] key) {bucket[j 1] bucket[j];j j - 1;}bucket[j 1] key;}
}// 桶排序函数
void bucketSort(int arr[], int n, int bucketCount) {int min arr[0], max arr[0];for (int i 1; i n; i) {if (arr[i] min) min arr[i];if (arr[i] max) max arr[i];}double bucketRange (double)(max - min 1) / bucketCount;int** buckets (int**)malloc(bucketCount * sizeof(int*));for (int i 0; i bucketCount; i) {buckets[i] (int*)malloc(n * sizeof(int));}for (int i 0; i n; i) {int bucketIndex (int)((arr[i] - min) / bucketRange);buckets[bucketIndex][0];buckets[bucketIndex][buckets[bucketIndex][0]] arr[i];}int index 0;for (int i 0; i bucketCount; i) {insertionSort(buckets[i], buckets[i][0] 1);for (int j 1; j buckets[i][0]; j) {arr[index] buckets[i][j];}}for (int i 0; i bucketCount; i) {free(buckets[i]);}free(buckets);
}八、总结
排序算法复杂度及稳定性分析 数据结构排序算法的总结 冒泡排序 • 两两比较相邻元素若顺序不对则进行交换每一轮将最大元素“浮”到末尾。 选择排序 • 不断从待排序部分选择最小或最大元素放在已排序部分的末尾。 插入排序 • 逐个将元素插入已排序的合适位置。 快速排序 • 选择一个基准元素通过划分操作将数组分为两部分递归地对两部分进行排序。 归并排序 • 不断将数组分成两半对两半分别排序再将排序好的两部分合并。 堆排序 • 先构建最大堆然后不断取出堆顶元素并调整堆实现排序。 希尔排序 • 基于插入排序通过不断缩小增量进行分组插入排序。 这些排序算法各有特点 • 时间复杂度方面冒泡、选择、插入排序在最坏情况下为 快速、归并、堆排序在平均和最坏情况下有更好的性能。 • 空间复杂度上有些是原地排序如冒泡、选择、插入、快速、希尔排序而归并排序等可能需要额外空间。 • 稳定性方面也各有不同比如冒泡、插入排序是稳定的而快速排序通常不稳定。 在实际应用中需要根据数据规模、特点以及具体需求来选择合适的排序算法。
