网站的所有权,免费网站空间怎么办,佛山市 骏域网站建设,泉州官方网站目录 排序的相关概念 排序#xff1a; 稳定性#xff1a; 内部排序#xff1a; 外部排序#xff1a; 常见的排序#xff1a; 常见排序算法的实现 插入排序#xff1a; 基本思想#xff1a; 直… 目录 排序的相关概念 排序 稳定性 内部排序 外部排序 常见的排序 常见排序算法的实现 插入排序 基本思想 直接插入排序 希尔排序缩小增量排序 选择排序 基本思想 直接选择排序 堆排序 交换排序 基本思想 冒泡排序 快速排序 Hoare版本 挖坑法 前后指针法: 快排递归优化 Hoare版本优化: 挖坑法优化: 前后指针优化 非递归快排 归并排序 基本思想 递归版本 非递归版本 计数排序 基本思想: 总结 排序的相关概念
排序
所谓排序就是使用一定的方法使一段可排序的序列变得有一定的顺序递增或递减。
稳定性
假定在待排序的序列中存在多个具有相同的关键字的元素若经过排序这些元素的相对次 序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。
内部排序
数据元素全部放在内存中进行排序。
外部排序
数据元素太多无法同时全部放进内存中进行排序。因此需要将待排序的数据存储在外存磁盘上排序时再把数据一部分一部分地调入内存中进行排序在排序过程中需要多次进行内存和外存之间地交换。这种排序方法就称作外部排序。
常见的排序 常见排序算法的实现
插入排序
基本思想
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。
日常生活中玩扑克牌拼牌时就用到了插入排序。 直接插入排序
当插入第i(i1)个元素时前面的i-1个元素已经排好序此时用a[i]的值依次与a[i-1],a[i-2],…,a[0]的值进行比较找到插入位置即将a[i]插入原来位置上的元素顺序后移。
排序过程如下图所示 代码如下
void InsertSort(int* a, int n)
{assert(a);int i 0, j 0;for (i 1; i n; i)//从第二个元素开始依次与前边的元素比较{int tem a[i];j i - 1;while (j 0){if (a[j] tem){a[j 1] a[j];}else{break;}j--;}a[j 1] tem;}
}特性总结 1. 元素集合越接近有序直接插入排序算法的时间效率越高 2. 时间复杂度O(N^2) 3. 空间复杂度O(1) 4. 稳定性稳定 希尔排序缩小增量排序
先选定一个整数gap把待排序数据分成gap个组所有距离为gap的数据分在同一组内并对每一组内的记录进行排序。然后缩小gap重复上述分组和排序的工作。当到达gap1时所有数据在同一组内排好序。
排序过程如下 代码如下
void ShellSort(int* a, int n)
{assert(a);int gap n;while (gap 1){gap / 2;//一组一组排序/*int i 0;for (i 0; i gap; i){int j 0;for (j i; j n - gap; j gap)//排一组{int front j;int back j gap;int tem a[back];//记录back位置原始数据while (front 0){if (tem a[front]){a[back] a[front];front - gap;back - gap;}else{break;}}a[front gap] tem;}}*///多组同时排序int j 0;for (j 0; j n - gap; j )//多组同时排{int front j;int back j gap;int tem a[back];//记录back位置原始数据while (front 0){if (tem a[front]){a[back] a[front];front - gap;back - gap;}else{break;}}a[front gap] tem;}}}
特性总结 1. 希尔排序是对直接插入排序的优化。 2. 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。 3. 时间复杂度希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算但有一个大致的范围O(N^1.3)~O(N^2) 4.空间复杂度O(1) 选择排序
基本思想
每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置或末尾位置直到全部待排序的数据元素排完。
直接选择排序
在元素集合a[i]--a[n-1]中选择最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换在剩余的a[i]--a[n-2]a[i1]--a[n-1]集合中重复上述步骤直到集合剩余1个元素。
排序过程如下 代码如下
void swap(int* p1, int* p2)//交换函数
{int k *p1;*p1 *p2;*p2 k;
}void SelectSort(int* a, int n)
{assert(a);//每次选最小的放前边//int i 0, j 0;//int mini 0;//最小数的下标//for (j 0; j n; j)//{// mini j;// for (i j 1; i n; i)// {// if (a[i] a[mini])// {// mini i;// }// }// swap(a[mini], a[j]);//}//优化--一次选出区间中最大的和最小的,分别插入头部和尾部int begin 0, end n - 1;while (begin end){int maxi end, mini begin;//最大最小值的下标int i begin;for (; i end; i){if (a[i] a[mini]){mini i;}if (a[i] a[maxi]){maxi i;}}swap(a[begin], a[mini]);if (maxi begin)//防止原begin位置是最大值被换到mini位置{maxi mini;}swap(a[end], a[maxi]);begin;end--;}
}
特性总结 1. 直接选择排序思考非常好理解但是效率不是很好实际中很少使用 2. 时间复杂度O(N^2) 3. 空间复杂度O(1) 4. 稳定性不稳定 堆排序
堆排序即利用堆的思想来进行排序思路如下1. 建堆 升序建大堆 降序建小堆2. 利用堆删除思想来进行排序 因为堆顶元素一定是最大值或最小值每次把堆顶元素与最后一个元素交换然后把数组尾指针向前移动1再对新的堆顶元素进行向下调整重复上述操作直至数组尾指针指向第一个元素此时的数组中的数据就是一个有序的序列。
代码如下
void swap(int* p1, int* p2)//交换函数
{int k *p1;*p1 *p2;*p2 k;
}//向下调整建大堆
void HeapDown(int* a, int parent, int n)
{assert(a);int child parent * 2 1;//左孩子while (child n){if (child1 n a[child] a[child 1])//找到大的{child 1;}if (a[child] a[parent])//大的孩子取代父亲{swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}//堆排序
void HeapSort(int* a, int n)
{assert(a);int parent (n - 1 - 1) / 2;//建大堆for (parent; parent 0; parent--){HeapDown(a, parent, n);}//排序int end n - 1;while (end 0){swap(a[0], a[end]);//把最大的放最后从根向下调整HeapDown(a, 0, end);//从根向下调整end--;}}
特性总结 1. 堆排序使用堆来选数效率就高了很多。 2. 时间复杂度O(N*logN) 3. 空间复杂度O(1) 4. 稳定性不稳定 交换排序
基本思想
根据序列中两个元素值的比较结果来决定是否交换这两个元素在序列中的位置进而达到将值较大的元素向序列的尾部移动值较小的元素向序列的前部移动的目的。
冒泡排序
两两元素相比前一个比后一个大就交换直到将最大的元素交换到末尾位置这是第一趟排序第二趟找出第二大的语速放在倒数第二个位置……进行n-1趟排序后全部数据就是有序的了。
排序动图如下 代码如下
void swap(int* p1, int* p2)//交换函数
{int k *p1;*p1 *p2;*p2 k;
}//冒泡排序
void BubbleSort(int* a, int n)
{assert(a);int i 0, j 0;for (i 0; i n - 1; i){int flag 0;//标记是否进行过交换for (j 1; j n - i; j){if (a[j-1] a[j])//每次相邻两个交换{/*int k a[i];a[i] a[j];a[j] k;*/swap(a[j-1], a[j]);flag;}}if (flag 0){break;}}
}
特性总结 1. 冒泡排序是一种非常容易理解的排序 2. 时间复杂度O(N^2) 3. 空间复杂度O(1) 4. 稳定性稳定 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
Hoare版本 1、选最左边作key右边先走找到比key小的值 2、左边后走找到大于key的值 3、然后交换left和right的值 4、一直循环重复上述1 2 3步 5、两者相遇时的位置与最左边选定的key值交换因为是让右边先走保证了最后相遇时该位置的值一定是小于key的 排序过程如下 代码如下
void swap(int* p1, int* p2)//交换函数
{int k *p1;*p1 *p2;*p2 k;
}//Hoare
int PartSort1(int* a, int left, int right)
{int keyi left;while (left right){while (left right a[right] a[keyi])//找小{right--;}while (left right a[left] a[keyi])//找大{left;}swap(a[left], a[right]);}swap(a[keyi], a[left]);//因为是右边先开始循环则当leftright时a[left]一定小于a[keyi]return left;
}void QuickSort(int* a, int begin, int end)
{if (begin end){return;}int keyi PartSort1(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);}
挖坑法
创建变量key储存最左边值以最左边为第一个坑位不断填充坑位并不断改变坑位的位置直至左右指针相遇此时为最后一个坑位再把key填入。 代码入下
//挖坑法
int PartSort2(int* a, int left, int right)
{int key a[left];int hold left;//坑位while (left right){while (left right a[right] key){right--;}a[hold] a[right];hold right;//更新坑位while (left right a[left] key){left;}a[hold] a[left];hold left;//更新坑位}a[left] key;return left;
}void QuickSort(int* a, int begin, int end)
{if (begin end){return;}int keyi PartSort2(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}
前后指针法: 代码入下
void swap(int* p1, int* p2)//交换函数
{int k *p1;*p1 *p2;*p2 k;
}//前后指针
int PartSort3(int* a, int left, int right)
{int keyi left;int prev left;int cur left 1;//cur找比a[keti]小的就和prev后一个交换位置while (cur right){if (a[cur] a[keyi]){swap(a[prev], a[cur]);}cur;}swap(a[prev], a[keyi]);return prev;
}void QuickSort(int* a, int begin, int end)
{if (begin end){return;}int keyi PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}
快排递归优化
1.三数取中
快速排序对于数据是敏感的如果这个序列是非常无序杂乱无章的那么快速排序的效率是非常高的可是如果数列有序时间复杂度就会从O(N*logN)变为O(N^2)相当于冒泡排序了。若每趟排序所选的key都正好是该序列的中间值即单趟排序结束后key位于序列正中间那么快速排序的时间复杂度就是O(NlogN)但是这是理想情况当我们面对一组极端情况下的序列就是有序的数组选择左边作为key值的话那么就会退化为O(N^2)的复杂度所以此时我们选择首位置尾位置中间位置的数分别作为三数选出值大小在中间的数放到最左边这样选key还是从左边开始这样优化后就不会出现选到最大值或最小值的极端情况了。 2.小区间优化
随着递归深度的增加递归次数以每层2倍的速度增加这对效率有着很大的影响当待排序序列的长度分割到一定大小后继续分割的效率比插入排序要差此时可以使用插排而不是快排。
我们可以当划分区间长度小于10的时候用插入排序对剩下的数进行排序
Hoare版本优化:
void swap(int* p1, int* p2)//交换函数
{int k *p1;*p1 *p2;*p2 k;
}//三数取中
int GetMid(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else//a[mid]a[right]{if (a[left] a[right]){return right;}else{return left;}}}else//a[left]a[mid] {if (a[left] a[right]){return left;}else//a[left]a[right]{if (a[mid] a[right]){return right;}else{return mid;}}}
}int PartSort1(int* a, int left, int right)
{int mid GetMid(a, left, right);//三数取中swap(a[mid], a[left]);int keyi left;while (left right){while (left right a[right] a[keyi])//找小{right--;}while (left right a[left] a[keyi])//找大{left;}swap(a[left], a[right]);}swap(a[keyi], a[left]);//因为是右边先开始循环则当leftright时a[left]一定小于a[keyi]return left;
}void QuickSort(int* a, int begin, int end)
{if (begin end){return;}if (end - begin 1 10)//小区间优化{int keyi PartSort1(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);}else{InsertSort(a begin, end - begin 1);//调用直接插入排序}}挖坑法优化:
void swap(int* p1, int* p2)//交换函数
{int k *p1;*p1 *p2;*p2 k;
}//三数取中
int GetMid(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else//a[mid]a[right]{if (a[left] a[right]){return right;}else{return left;}}}else//a[left]a[mid] {if (a[left] a[right]){return left;}else//a[left]a[right]{if (a[mid] a[right]){return right;}else{return mid;}}}
}//挖坑法
int PartSort2(int* a, int left, int right)
{int mid GetMid(a, left, right);swap(a[mid], a[left]);int key a[left];int hold left;//坑位while (left right){while (left right a[right] key){right--;}a[hold] a[right];hold right;//更新坑位while (left right a[left] key){left;}a[hold] a[left];hold left;//更新坑位}a[left] key;return left;
}void QuickSort(int* a, int begin, int end)
{if (begin end){return;}if (end - begin 1 10)//小区间优化{int keyi PartSort2(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);}else{InsertSort(a begin, end - begin 1);//调用直接插入排序}}前后指针优化
void swap(int* p1, int* p2)//交换函数
{int k *p1;*p1 *p2;*p2 k;
}int PartSort3(int* a, int left, int right)
{int keyi left;int prev left;int cur left 1;//cur找比a[keti]小的就和prev后一个交换位置while (cur right){if (a[cur] a[keyi]){swap(a[prev], a[cur]);}cur;}swap(a[prev], a[keyi]);return prev;
}void QuickSort(int* a, int begin, int end)
{if (begin end){return;}if (end - begin 1 10)//小区间优化{int keyi PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);}else{InsertSort(a begin, end - begin 1);//直接调用插入排序}}
非递归快排
当数据量较大时一直递归调用就会一直开辟栈帧增加栈的消耗因此我们可以人工创建一个栈结构代替递归调用开辟新的栈帧。
关于栈我在栈和队列详解中有详细介绍在这里就不再过多介绍。
具体思路如下 1. 申请一个栈将整个数组的起始位置和终点位置入栈起始位置先进栈。 2. 利用栈的特性后进先出末位置后进栈所以末位置先出栈。 定义right、left接收的靠近栈顶的两个元素作为排序序列的始末位置。 3. 对数组进行一次单趟排序返回一个下标keyi。 4. 此时待排序列被分为[left,keyi-1],keyi,[keyi1,right]三段再把左右两边区间的始末位置入栈若该区间合法要求区间起始位置先进栈。 5. 重复2、3、4操作直至栈内为空。 代码如下
//快速排序非递归
void QuickSortNonr(int* a, int n)
{ST st;STInit(st);//栈储存[0,n-1]区间左右下标先入右下标后入左下标STPush(st, n - 1);STPush(st, 0);while (!STEmpty(st)){int left STTop(st);STPop(st);int right STTop(st);STPop(st);int keyi PartSort3(a, left, right);//[left,right]区间分为[left,keyi-1],keyi,[keyi1,right]if (keyi 1 right)//入[keyi1,right]区间下标{STPush(st, right);STPush(st, keyi 1);}if (keyi - 1 left)//入[left,keyi-1]区间下标{STPush(st, keyi - 1);STPush(st, left);}}STDestroy(st);
}特性总结 1. 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序 2. 时间复杂度O(N*logN) 3. 空间复杂度O(logN) 4. 稳定性不稳定 归并排序
基本思想
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide andConquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再合并子序列并保证其有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 递归版本
void MerSort(int* a, int* tem, int left, int right)
{if (left right){return;}//递归划分区间int mid (left right) / 2;MerSort(a, tem, left, mid);MerSort(a, tem, mid 1, right);//归并到tem数组int begin1 left, end1 mid;int begin2 mid 1, end2 right;int index begin1;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tem[index] a[begin1];}else{tem[index] a[begin2];}}while (begin1 end1){tem[index] a[begin1];}while (begin2 end2){tem[index] a[begin2];}//拷贝回原数组---因为每次都要从原数组中归并到tem数组中因此每次归并完后都要拷贝回原数组memcpy(a left, tem left, sizeof(int) * (right - left 1));
}
//归并排序
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);exit(-1);}MerSort(a, tmp, 0, n - 1);free(tmp);
}
非递归版本
与快排类似当数据量较大时一直递归调用会增加栈的消耗因此我们可以考虑改非递归的方法实现。
归并改非递归时可以定义一个gap作为每次归并的区间长度一趟归并后再把gap乘以2作为新的归并区间长度继续归并直至全部归并完成。其关键在于对边界的控制 代码如下
//归并排序(非递归)
void MergeSortNonr(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);exit(-1);}int gap 1;//每次归并的长度while (gap n){int i 0;for (i 0; i n; i gap * 2){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i gap gap - 1;if (begin2 n || end1 n)//要归并的第二个区间不存在直接退出{//memcpy(tmp i, a i, sizeof(int) * (n - i));//把不归并的数据提前拷贝进tmp数组防止因为a数组没有全部进行归并tmp数组中存在随机值//进而导致后续把tmp数组数据拷贝进a数组时拷贝随机数据进a数组break;}if (end2 n)//要归并的第二个区间右边越界重置右区间{end2 n - 1;}//printf([%d,%d][%d,%d], begin1, end1, begin2, end2);//打印每次归并区间int index begin1;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[index] a[begin1];}else{tmp[index] a[begin2];}}while (begin1 end1){tmp[index] a[begin1];}while (begin2 end2){tmp[index] a[begin2];}memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));//每次归并完成后把tmp中数据拷贝进a数组防止丢失数据}//memcpy(a, tmp, sizeof(int) * n);//一趟归并后再把tmp数组的数据拷贝进a数gap * 2;}free(tmp);
}
特性总结 1. 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。 2. 时间复杂度O(N*logN) 3. 空间复杂度O(N) 4. 稳定性稳定 计数排序
基本思想:
遍历数组统计数组中每个元素的出现频率再按顺序放回原数组。 需要注意的是由于待排序列不一定是从0开始的且不知道要创建多大的数组进行计数因此在遍历数组统计频率时要同时找出最大最小值每次计数时用该位置数值减去最小值即为该数对应的下标用最大值减去最小值再加1就是要创建的计数数组的大小。
代码如下
// 计数排序
void CountSort(int* a, int n)
{int min a[0];int max 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*)malloc(sizeof(int) * range);if (count NULL){perror(malloc fail);exit(-1);}memset(count, 0, sizeof(int) * range);//每个数减去min就是对应的下标for (int i 0; i n; i){count[a[i] - min];}//重新写入原数组下标min就是原始值int i 0;for (int j 0; j range; j){while (count[j]--){a[i] j min;}}free(count);
}特性总结 1. 计数排序在数据范围集中时效率很高但是适用范围及场景有限。 2. 时间复杂度O(MAX(N,范围)) 3. 空间复杂度O(范围) 4. 稳定性稳定 总结
