网站建设与网页制作技术,网站建设内容介绍,wordpress 调整字体,沈阳市城市建设网站文章目录 排序什么是排序排序的分类1. 冒泡1.1 冒泡排序1.2. 快速排序 2. 选择2.1 简单选择排序2.2 堆排序 3. 插入3.1 直接插入3.2 折半插入3.3 希尔排序 4. 归并排序代码实现 5. 基数排序 排序图片就不贴了吧 排序 什么是排序
以下部分动图来自CSDN
::: tip 稳定性的概念
… 文章目录 排序什么是排序排序的分类1. 冒泡1.1 冒泡排序1.2. 快速排序 2. 选择2.1 简单选择排序2.2 堆排序 3. 插入3.1 直接插入3.2 折半插入3.3 希尔排序 4. 归并排序代码实现 5. 基数排序 排序图片就不贴了吧 排序 什么是排序
以下部分动图来自CSDN
::: tip 稳定性的概念
定义能保证两个相等的数经过排序之后其在序列的前后位置顺序不变。A1A2排序前A1在A2前面排序后A1还在A2前面
意义稳定性本质是维持具有相同属性的数据的插入顺序如果后面需要使用该插入顺序排序则稳定性排序可以避免这次排序。 :::
排序的分类
1. 冒泡
1.1 冒泡排序
一个一个往上冒
:::details 查看代码
func BubbleSort(arr []int) []int {n : len(arr)for i : 0; i n-1; i {for j : i 1; j n; j {if arr[i] arr[j] {arr[i], arr[j] arr[j], arr[i]}}}return arr
}
for(int i0; ik-1; i)for(int ji1; jk; j){if(arr[j]arr[i]){ // 从小到大arr[i] ^ arr[j];arr[j] ^ arr[i];arr[i] ^arr[j];}}:::
1.2. 快速排序 升级版冒泡递归 基本思想 通过一趟排序将待排的数据分割成两部分其中一部分的数据均比另一部分的数据要小对两组数据进行排序。 :::details 查看代码
func QuickSort(a []int) []int {n : len(a)if n 1 {return a}left : make([]int, 0)right : make([]int, 0)guard : a[0]for i : 1; i n; i {if a[i] guard {left append(left, a[i]) // 比哨兵小入左队} else {right append(right, a[i]) // 其他入大队}}left, right QuickSort(left), QuickSort(right)res : append(append(left, guard), right...)return res
}// 左闭右开
func QuickSort1(a []int, left, right int) {if left right-1 {return}low : lefthigh : right - 1guard : a[low]for low high {/*小的往左大的往右*/for low high a[high] guard {high--}a[low] a[high]for low high a[low] guard {low}a[high] a[low]}a[low] guardQuickSort1(a, left, low)QuickSort1(a, low1, right)
}void q_sort(int a[], int left, int right){
// left, right 左闭右开 low、high闭区间
// a[left] 即左边第一个元素为哨兵if(left right-1 ) return;int low left, high right-1, center a[low];// 直到lowhigh 确保左边的元素都比右边的小while( low high ){// 从右边开始往回搜索找到第一个比哨兵小的元素,比哨兵大则跳过while( lowhigh a[high] center ) high --;// 将比哨兵小的元素移动到左边a[low] a[high];// 从左边往右边搜索 找到第一个比哨兵大的元素比哨兵小则跳过while( low high a[low] center) low;// 将比哨兵大的元素移动到右边a[high] a[low];}// 把哨兵存入分界线位置a[low] center; // a[high] center;// 开始递归快排q_sort(a, left, low); // 左边q_sort(a, low1, right ); // 右边
}快排优化版的简单示意图(以 3 5 2 1 6作为局部数组为例)
:::
2. 选择
2.1 简单选择排序
选择最小的往前放
:::details 查看代码
func SelectSort(a []int) []int {n : len(a)for i : 0; i n-1; i {minIndex : ifor j : i 1; j n; j {if a[j] a[minIndex] {minIndex j}}if minIndex ! i {a[minIndex], a[i] a[i], a[minIndex]}}return a
}
// 从小到大
for(int i0; ilength-1; i){minIndexi;for(int ji1; jlength{if(arr[j]arr[minIndex]) minIndexj; // 选择最小的元素的下标}if( minIndex ! i){arr[i]^arr[minIndex];arr[minIndex] ^arr[i];arr[i] ^ arr[minIndex];}
}
这里有一个小小的优化技巧 在搜索最小数下标的时候同时搜索最大数的下标可以使得复杂度减半。 :::
2.2 堆排序
::: details 先来了解下堆的相关概念
堆是具有以下性质的完全二叉树 每个结点的值都大于或等于其左右孩子结点的值称为大顶堆 或者每个结点的值都小于或等于其左右孩子结点的值称为小顶堆。 如下图
同时我们对堆中的结点按层进行编号将这种逻辑结构映射到数组中就是下面这个样子
该数组从逻辑上讲就是一个堆结构我们用简单的公式来描述一下堆的定义就是
大顶堆arr[i] arr[2i1] arr[i] arr[2i2] (小到大排序)
小顶堆arr[i] arr[2i1] arr[i] arr[2i2] 大到小排序
:::
:::details 堆的百度百科 堆heap是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。
堆总是满足下列性质
堆中某个结点的值总是不大于或不小于其父结点的值堆总是一棵完全二叉树。
:::details 完全二叉树
完全二叉树的特点 叶子结点只能出现在最下层和次下层且最下层的叶子结点集中在树的左部。
需要注意的是满二叉树肯定是完全二叉树而完全二叉树不一定是满二叉树
判断一棵树是否是完全二叉树的思路 1如果树为空则直接返回错 2如果树不为空层序遍历二叉树 2.1如果一个结点左右孩子都不为空则pop该节点将其左右孩子入队列 2.1如果遇到一个结点左孩子为空右孩子不为空则该树一定不是完全二叉树 2.2如果遇到一个结点左孩子不为空右孩子为空或者左右孩子都为空且则该节点之后的队列中的结点都为叶子节点该树才是完全二叉树否则就不是完全二叉树. ::: 了解了这些定义。接下来看看堆排序的基本思想及基本步骤
堆排序基本思想及步骤
基于选择排序 堆排序的基本思想是将待排序序列构造成一个大顶堆此时整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆这样会得到n个元素的次小值。如此反复执行便能得到一个有序序列了 :::details 查看代码
// 构建小顶堆 大到小排序// 交互a数组中的x跟y
void swap(int a[], int x, int y){a[x] ^ a[y];a[y] ^ a[x];a[x] ^ a[y];
}// 调整堆
void heapAdjust(int a[], int i, int len){int flag a[i];for(int j2*i; jlen; j*2 ){if( jlen a[j]a[j1] ) j;if( flag a[j] ) break;a[i] a[j]; ij;}a[i] flag;
}// 堆排序
void heapSort(int a[], int len){for(int ilen/2; i0; --i){heapAdjust(a, i, len);}for(int ilen; i1; i--){swap(a, 1, i);heapAdjust(a, 1, i-1);}
}
:::
3. 插入
::: tip 与现实场景的联系 存在一个已经排好的队伍从矮到高这时来了个还没排的家伙他需要去找他需要站的位置。
:::
3.1 直接插入
从后往前 默认前面已排好序假设j前面j-1的元素已经是有序的接下来要对a[j] 的位置查找
:::details 查看代码
func InsertSort(a []int) []int {n : len(a)for i : 1; i n; i {for j : i; j 0 a[j] a[j-1]; j-- {a[j-1], a[j] a[j], a[j-1]}}return a
}// 从小到大
for(int i1; ilength; i){for(int ji; (j0) ( arr[j]arr[j-1] ); j--){arr[j]^arr[j-1];arr[j-1] ^ arr[j];arr[j] ^arr[j-1];}
}
:::
3.2 折半插入 从1开始对后面的元素进行折半查找插入 :::details 查看代码
func BinarySearchInsertSort(a []int) []int {n : len(a)var low, high, mid, reg intfor i : 1; i n; i {low 0high i - 1reg a[i]for low high {mid (low high) 1if reg a[mid] {low mid 1} else {high mid - 1}}/*low是还没排序的元素应该去的位置所以low后面已排序的元素都要往后站*/for j : i; j low; j-- {a[j] a[j-1]}a[low] reg}return a
}// 降序从大到小
void z_sort(int a[], int len){int low 0,high 0,mid;int temp 0;for (int i1; ilen; i) {low0;highi-1;tempa[i]; // 要插入的元素while (lowhigh) {mid(lowhigh)1;// 决定顺序的位置if (a[mid]temp) {highmid-1;}else{lowmid1;}}// 把元素后移for (int ji; jlow; j--) {a[j]a[j-1];}a[low]temp;//插入元素}
}:::
3.3 希尔排序
::: tip 百度百科 希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”Diminishing Increment Sort是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。 希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至 1 时整个文件恰被分成一组算法便终止。 希尔排序是基于插入排序的以下两点性质而提出改进方法的
插入排序在对几乎已经排好序的数据操作时效率高即可以达到线性排序的效率。但插入排序一般来说是低效的因为插入排序每次只能将数据移动一位。 ::: 希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至1时整个文件恰被分成一组算法便终止。 重点注意对每个子序列进行插入排序
:::details 查看代码
func shellSort(a []int) []int {n : len(a)/*gap: 增量每次减半*/for gap : n 1; gap 1; gap 1 {for i : gap; i n; i gap {for j : i; j 0 a[j] a[j-gap]; j - gap {a[j-gap], a[j] a[j], a[j-gap]}}}return a
}void shellSort(int* a, int n)
{int i,gap,j;// gap为步长每次减为原来的一半。for (gap n / 2; gap 1 ; gap / 2){// 组内排序for (i gap ;i n; i gap) {for(j i; j0 a[j] a[j-gap]; j- gap) {swap(a[j-gap], a[j]);}}}
}:::
4. 归并排序
基本思想
归并排序是用分治思想分治模式在每一层递归上有三个步骤
分解Divide将n个元素分成个含n/2个元素的子序列。解决Conquer用合并排序法对两个子序列递归的排序。合并Combine合并两个已排序的子序列已得到排序结果。
实现逻辑
2.1 迭代法 ① 申请空间使其大小为两个已经排序序列之和该空间用来存放合并后的序列 ② 设定两个指针最初位置分别为两个已经排序序列的起始位置 ③ 比较两个指针所指向的元素选择相对小的元素放入到合并空间并移动指针到下一位置 ④ 重复步骤③直到某一指针到达序列尾 ⑤ 将另一序列剩下的所有元素直接复制到合并序列尾 2.2 递归法 ① 将序列每相邻两个数字进行归并操作形成floor(n/2)个序列排序后每个序列包含两个元素 ② 将上述序列再次归并形成floor(n/4)个序列每个序列包含四个元素 ③ 重复步骤②直到所有元素排序完毕 动图演示 归并排序演示
具体的我们以一组无序数列141215131116为例分解说明如下图所示
上图中首先把一个未排序的序列从中间分割成2部分再把2部分分成4部分依次分割下去直到分割成一个一个的数据再把这些数据两两归并到一起使之有序不停的归并最后成为一个排好序的序列。
文字版
:::details
有序数组A[3 8 9 11 13]
有序数组B[1 5 8 10 17 19 20 23]
[] 表示比较的范围。因为 1 3所以 1 加入辅助数组
有序数组A[3 8 9 11 13]
有序数组B1 [5 8 10 17 19 20 23]
辅助数组1因为 3 5所以 3 加入辅助数组
有序数组A3 [8 9 11 13]
有序数组B1 [5 8 10 17 19 20 23]
辅助数组1 3因为 5 8所以 5 加入辅助数组
有序数组A3 [8 9 11 13]
有序数组B1 5 [8 10 17 19 20 23]
辅助数组1 3 5
因为 8 8所以 两个数都 加入辅助数组有序数组A3 8 [9 11 13]
有序数组B1 5 8 [10 17 19 20 23]
辅助数组1 3 5 8 8
因为 9 10所以 9 加入辅助数组有序数组A3 8 9 [11 13]
有序数组B1 5 8 [10 17 19 20 23]
辅助数组1 3 5 8 8 9因为 10 11所以 10 加入辅助数组
有序数组A3 8 9 [11 13]
有序数组B1 5 8 10 [17 19 20 23]
辅助数组1 3 5 8 8 9 10因为 11 17所以 11 加入辅助数组
有序数组A3 8 9 11 [13]
有序数组B1 5 8 10 [17 19 20 23]
辅助数组1 3 5 8 8 9 10 11因为 13 17所以 13 加入辅助数组
有序数组A3 8 9 11 13
有序数组B1 5 8 10 [17 19 20 23]
辅助数组1 3 5 8 8 9 10 11 13因为数组A已经没有比较元素将数组B剩下的元素拼接在辅助数组后面。
结果1 3 5 8 8 9 10 11 13 17 19 20 23:::
代码实现
自顶向下归并(递归)
:::details 查看代码
// 二路归并
func MergeSort(a []int) []int {n : len(a)if n 1 {return a}mid : n 1left, right : MergeSort(a[:mid]), MergeSort(a[mid:])return merge(left, right)
}func merge(left, right []int) (res []int) {l, r : 0, 0len_l, len_r : len(left), len(right)for l len_l r len_r {if left[l] right[r] {res append(res, left[l])l} else {res append(res, right[r])r}}// 把两个子切片的剩余元素直接入队res append(append(res, left[l:]...), right[r:]...)return
}
// 归并排序C-递归版void merge_sort_recursive(int arr[], int reg[], int start, int end) {if (start end)return;int len end - start, mid (len / 2) start;int start1 start, end1 mid;int start2 mid 1, end2 end;merge_sort_recursive(arr, reg, start1, end1);merge_sort_recursive(arr, reg, start2, end2);int k start;// 决定是降序还是升序while (start1 end1 start2 end2)reg[k] arr[start1] arr[start2] ? arr[start1] : arr[start2];while (start1 end1)reg[k] arr[start1];while (start2 end2)reg[k] arr[start2];for (k start; k end; k)arr[k] reg[k];
}
void merge_sort(int arr[], const int len) {int *reg new int[len1];merge_sort_recursive(arr, reg, 0, len - 1);delete[] reg;
}:::
自底向上归并迭代
:::details 查看代码
func MergeSort(a []int, begin, end int) {step : 1// 步数为1开始step长度的数组表示一个有序的数组// 1 - 2 - 4 - 8for end-begin step {// 从头到尾对数组进行归并操作// step 1 2 * step 表示偏移到后两个有序数组将它们进行归并for i : begin; i end; i step 1 {low : imid : low stephigh : low (step 1)// 不存在第二个数组直接返回if mid end {return}// 第二个数组长度不够if high end {high end}// 合并两个有序的数组merge(a, low, mid, high)}step 1}
}func merge(a []int, begin, mid, end int) {leftSize : mid - beginrightSize : end - midnewSize : leftSize rightSizeresult : make([]int, 0, newSize)l, r : 0, 0for l leftSize r rightSize {lval : a[beginl]rval : a[midr]if lval rval {result append(result, lval)l} else {result append(result, rval)r}}result append(result, a[beginl:mid]...)result append(result, a[midr:end]...)for i : 0; i newSize; i {a[begini] result[i]}return
}void mergeSort(int a[], int reg[], const int end){// 分for(int step1; stepend; step*2){for(int j0; j end; j step*2 ){int low j, mid jstep-1, high min(j2*step-1, end-1);merge(a, reg, low, mid, high );}}
}void merge(int a[], int reg[], int l, const int mid, const int r){int start l;int end r;int j mid1;int i l;while( i mid j r ){reg[l] a[i]a[j] ? a[i] : a[j];}while(imid) reg[l] a[i];while(jr) reg[l] a[j];for(int iistart; iiend; ii){a[ii] reg[ii];}
}
:::
5. 基数排序
:::details 查看代码
func getbits(a []int) int {max_num : 0for _, v : range a {if v max_num {max_num v}}res : 0if max_num 0 {return 1}for max_num 0 {max_num / 10res}return res
}func radixSort(a []int) {n : len(a)step : getbits(a)radix : 1var num, tail intreg : make([][]int, 10)for i : 0; i step; i {radix * 10// 每一轮都要清空桶for i : 0; i 10; i {reg[i] make([]int, 0)}for j : 0; j n; j {num a[j] % radixtail num / (radix / 10)reg[tail] append(reg[tail], a[j])}index : 0for k : 0; k 10; k {for _, v : range reg[k] {a[index] vindex}}}
}#includeiostream
using namespace std;int maxbit(int data[], int n) //辅助函数求数据的最大位数
{int d 1; //保存最大的位数int p 10;for(int i 0; i n; i){while(data[i] p){p * 10;d;}}return d;
}
void radixSort(int data[], int n) //基数排序
{// d 位int d maxbit(data, n);int *tmp new int[n5];int *count new int[10]; //计数器 -- 排序桶int *flag new int[10];int i, j, k;int radix 1;for(i 1; i d; i) //进行d次排序{for(j 0; j 10; j){count[j] 0; //每次分配前清空计数器清桶tmp[j] -1;flag[j] 0;}for(j 0; j n; j){// k 是当前数字位置中的数字k (data[j] / radix) % 10; //统计每个桶中的记录数count[k];}for(int jj0; jj10; jj){flag[jj] count[jj];}for(j 1; j 10; j)count[j] count[j - 1] count[j]; //将tmp中的位置依次分配给每个桶for(j n - 1; j 0; j--) //将所有桶中记录依次收集到tmp中{k (data[j] / radix) % 10;tmp[count[k] - 1] data[j];count[k]--;}for(j 0; j n; j){//将临时数组的内容复制到data中data[j] tmp[j];}radix radix * 10;}delete[]tmp;delete[]count;
}
:::
