网站设计做图工具,wordpress对联,建站快车管理,wordpress移动端音乐插件目录
一.排序的基本概念
1.1.什么是排序
1.2.排序算法的评价指标
1.3.排序的分类
二.插入排序
2.1.直接插入排序
2.2.希尔排序
三.选择排序
3.1.直接选择排序
3.2.堆排序
重建堆
建堆
排序
四.交换排序
4.1.冒泡排序
4.2.快速排序
快速排序的递归实现
法一hoara法
法二挖坑法
法三前后指针法
快速排序优化
三数取中法选key
小区间非递归优化
快速排序的非递归实现
五.归并排序
归并排序的递归实现
归并排序的非递归实现
六.非比较排序 一.排序的基本概念 1.1.什么是排序
排序(Sort)就是重新排列表中的元素使表中的元素满足按关键字有序的过程。
输入n个记录R1,R2,Rn对应的关键字为k1,k2,.,kn。 输出输入序列的一个重排R1,R2,…,R’,使得有k1≤k2≤...≤kn(也可递减)。
1.2.排序算法的评价指标
1.时间复杂度空间复杂度
2.稳定性。
若待排序表中有两个元素Ri和Rj其对应的关键字相同即keyikeyj且在排序前Ri在Rj的前面若使用某一排序算法排序后Ri仍然在Rj的前面则称这个排序算法是稳定的否则称排序算法是不稳定的。 1.3.排序的分类
排序算法可以分为
内部排序数据都在内存中外部排序数据太多无法全部放入内存。
之所以有这种分类是因为磁盘的容量一般远大于内存而运算速度又远不如内存。因此排序算法不仅要关注时间和空间复杂度有时考虑到内存容量的问题还要关注如何使读/写磁盘次数更少。 二.插入排序
插入排序的基本思想在一个已排好序的记录子集的基础上每一步将下一个待排序的记录有序插入到已排好序的记录子集中直到将所有待排记录全部插入为止。
2.1.直接插入排序
直接插入排序是一种最基本的插入排序方法其基本操作是将第i个记录插入到前面i-1个已排好序的记录中。
具体过程将第i个记录的关键字Ki顺次与其前面记录的关键字Ki-1,Ki-2,…,K1进行比较将所有关键字大于Ki的记录依次向后移动一个位置直到遇见一个关键字小于或者等于Ki的记录Kj此时Kj后面必为空位置将第i个记录插人空位置即可。
完整的直接插人排序是从i2开始的也就是说将第一个记录视为已排好序的单元素子集合然后将第二个记录插入到单元素子集合中。i从2循环到n即可实现完整的直接插入排序。 实现
void InsertSort(int* a, int n)
{//[0,end]有序把end1位置的值插入继续保持数组有序(升序)for (int i 0; i n - 1; i){//单趟排序int end i;//有序数组的最后一个元素的下标int tmp a[end 1];//tmp为待插入元素while (end 0){if (tmp a[end])//若待插入元素小于有序数组中的最后一个元素{a[end 1] a[end];//将最后一个元素往后移动一位--end;//与有序数组的前一个元素继续比较}else{break;}}//1.break出来也就是tmpa[end]//2.break出来也就是tmp比所有的值都小end--之后变为-1小于0a[end 1] tmp;}
}
运行结果 算法分析
空间复杂度O(1)。只需要定义几个所需空间为常数级的辅助变量(如i,j,tmp,a[0])与问题的规模n无关。
时间复杂度主要来自对比关键字移动元素若有n个元素则需要n-1趟处理。
最好情况数组原本就有序O(N)。每一趟while循环只执行一次只需要对比关键字1次不用移动元素。最坏情况数组原本逆序O(N^2)。while循环中关键字比较次数和移动记录的次数为i-1。
稳定性稳定。在直接插入排序算法中由于待插入元素的比较是从后向前进行的循环的判断条件就保证了后面出现的关键字不可能插入到与前面相同的关键字之前因此保证了直接插入排序方法的稳定性。
小结
直接插入排序算法简单比较适用于待排序记录数目较少且基本有序的情况
2.2.希尔排序
希尔排序又称缩小增量排序法是一种基于插入思想的排序方法它利用了直接插入排序的最佳性质。首先将待排序的关键字序列分成若干个较小的子序列然后对子序列进行直接插入排序最后再对全部记录进行一次直接插入排序。
首选选定记录间的距离为di(i1)在整个待排序记录序列中将所有间隔为d1的记录分成一组进行组内直接插入排序然后取ii1记录间的距离为di(didi-1)在整个待排序记录序列中将所有间隔为di的记录分成一组进行组内直接插入排序。重复步骤2多次直至记录间的距离di1此时整个只有一个子序列对该序列进行直接插入排序完成整个排序过程。
注意
当子序列记录间的间隔为d时共有d个子序列需要对d个子序列分别进行插入排序。但是算法在具体实现时并不是先对一个子序列完成插入排序再对另一个子序列进行插入排序而是从第一个子序列的第二个记录开始顺序扫描整个待排序记录序列当前记录属于哪一个子序列就在哪一个子序列中进行插入排序。
当从第一个子序列的第二个记录开始顺序扫描整个待排序记录序列时各子序列的记录将会轮流出现所以算法将会在每一个子序列中轮流进行插入排序。 步骤
预排序(接近顺序有序)。分gap组预排大的数据更快到后面小的数据更快到前面直接插入排序(有序)。
预排序法一
先对一个子序列完成插入排序再对另一个子序列进行插入排序
void ShellSort(int* a, int n)
{//取gap为3int gap 3;//一组排完再排下一组for (int j 0; j gap; j){for (int i j; i n - gap; i gap){//每组内进行直接插入排序int end i;int tmp a[end gap];while (end 0){//升序if (tmp a[end]){//将大的数往后移小的数往前移a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}运行结果 预排序法二
顺序扫描整个待排序记录序列当前记录属于哪一个子序列就在哪一个子序列中进行插入排序
void ShellSort(int* a, int n)
{//取gap为3int gap 3;//每个子序列先排前两个元素待所有子序列都排完之后再增加一个元素进行新的排序for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){//每组内进行直接插入排序if (tmp a[end]){//将大的数往后移小的数往前移a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}
}运行结果 关于增量的取法
关于增量d的取法最初希尔提出取d⌊d/2⌋再取d⌊d/2⌋直到d1为止。该思路的缺点是奇数位置的元素在最后一步才会与偶数位置的元素进行比较使得希尔排序效率降低。因此后来有人提出d⌊d/3⌋1。
排升序时gap越大大的数可以更快到后面小的数也可以更快到前面但是越不接近有序。 排升序时gap越小越接近有序当gap1时就是直接插入排序。
希尔排序实现
void ShellSort(int* a, int n)
{PrintArray(a, n);//gap大于1时是预排序gap最后一次等于1时是直接插入排序int gap n;while (gap 1){gap gap / 3 1;//1是为了保证最后的gap值为1为直接插入排序for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){//每组内进行直接插入排序if (tmp a[end]){//将大的数往后移小的数往前移a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}printf(gap:%d\n, gap);PrintArray(a,n);}
}运行结果 算法分析
空间复杂度O(1)。只需要定义几个所需空间为常数级的辅助变量(如i,j,tmp,a[0])与问题的规模n无关。
时间复杂度和增量序列d1,d2,d3,...的选择有关目前无法用数学手段证明确切的时间复杂度。最 坏时间复杂度为当n在某个范围内时可达O(N^1.3)。
稳定性不稳定。在排序过程中相同关键字记录的领先关系发生变化则说明该排序方法是不稳定的。例如有待排序序列{2,4,1,2}采用希尔排序设d12则有{2,4,1,2}得到一趟排序结果为{1,2,2,4}说明希尔排序法是不稳定的排序方法。
小结
希尔排序对于中等规模(n1000)的序列具有较高的效率且希尔排序算法简单容易执行。因此很多排序应用程序都选了希尔排序算法。
三.选择排序
每一次从待排序的数据元素中选出最小(或最大)的一个元素存放在序列的起始位置直到全部待排序的数据元素排完。
3.1.直接选择排序
具体过程
设begin 0为数组起始元素的下标end n - 1为数组末尾元素的下标通过遍历数组[begin,end]中找出其中的最大值和最小值并将最大值与数组末尾元素进行交换将最小值与数组起始元素进行交换此时最小值来到数组开头最大值来到数组末尾。然后将begin1来到数组起始第二个元素的位置并将其作为新的数组头将end-1来到数组末尾第二个元素的位置并将其作为新的数组尾继续遍历数组[begin,end]中找出其中的最大值和最小值并将最大值与数组末尾元素进行交换将最小值与数组起始元素进行交换。重复上述操作直到begin end时循环结束。
案例
对数组arr[6]{ 3,4,0,5,1,2 }进行直接插入排序
第一次排序begin 0,end 5数组arr[6] { 3,4,0,5,1,2 }最大值为5最小值为0排完序得arr[6] { 0,4,3,2,1,5 }第二次排序begin 1,end 4数组arr[6] { 0,4,3,2,1,5 }最大值为4最小值为1排完序得arr[6] { 0,1,3,2,4,5 }第三次排序begin 2,end 3数组arr[6] { 0,1,3,2,4,5 }最大值为3最小值为2排完序得arr[6] { 0,1,2,3,4,5 }第四次排序begin 3,end 2数组已有序排序完毕。
实现
void Swap(int* px, int* py)
{int tmp *px;*px *py;*py tmp;
}void SelectSort(int* a, int n)
{//判空assert(a);int begin 0;int end n - 1;while (begin end){int mini begin;//假设起始元素为最小值int maxi begin;//假设起始元素为最大值//从第二个元素开始比较找出数组中的最大值和最小值for (int i begin 1; i end; i){//若数组中存在一个比起始元素小的值if (a[i] a[mini]){mini i;}//若数组中存在一个比起始元素大的值if (a[i] a[maxi]){maxi i;}}//将最小值换到数组的起始位置Swap(a[begin], a[mini]);//如果begin和maxi重叠则要修正一下maxi的位置//如果begin所在下标的值为最大值在和较小元素互换之后最大值已不在begin所在下标的位置而是转到新的mini所在下标的位置if (begin maxi){maxi mini;}//将最大值换到数组的最后位置Swap(a[end], a[maxi]);begin;--end;}
}
注意
当最大值maxi和begin发生位置重叠时在进行最小值mini和begin交换过程中最大值maxi会被交换到最小值mini的位置。此时如果直接进行Swap(a[end], a[maxi])排序就会出现问题。因此在进行最大值maxi和end交换之前需要判断一下最大值maxi与begin的位置是否发生重叠若发生重叠则将最大值maxi进行更新然后再进行交换。
运行结果 算法分析
空间复杂度O(1)。只需要定义几个所需空间为常数级的辅助变量(如i,j,tmp,a[0])与问题的规模n无关。
时间复杂度假设要对n个数据进行选择排序则总共要进行n/2次最大值和最小值的筛选第一次排序要遍历n个数据第二次排序要遍历n-2个数据...最后一次排序要遍历2个数据或1个数据。设遍历一次数据就表示要进行一次排序操作则总共要进行的操作次数为 根据大O渐进法规则选择排序的时间复杂度为O(N^2)。
稳定性不稳定。在排序过程中相同关键字记录的领先关系发生变化则说明该排序方法是不稳定的。例如有待排序序列{3,3,2}采用选择排序第一次交换得{2,3,3}说明希尔排序法是不稳定的排序方法。
3.2.堆排序 堆排序的过程主要需要解决两个问题一是按堆定义建初堆二是去掉最大元之后重建堆得到次大元以此类推。
我们以升序建大堆为例
重建堆
向下调整建堆法
首先将数组中的元素以完全二叉树的形式排列好然后从倒数第一个非叶子结点开始调用函数AdjustDown依次向下调整。每调整一次则将i的值减1让其来到倒数第二个非叶子结点的位置重复上述操作直到i来到根结点的位置。
实现
//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{//1.选出左右孩子中小的那一个int child parent * 2 1;//假设左孩子最小while (child size){//当右孩子存在且右孩子小于左孩子if (child 1 size a[child 1] a[child])//大堆a[child1]a[child]{child;//则将右孩子置为child}//2.小的孩子跟父亲比较如果比父亲小则交换然后继续往下调整如果比父亲大则调整结束if (a[child] a[parent])//大堆a[child]a[parent]{//交换数据Swap(a[child], a[parent]);//3.继续往下调最多调整到叶子结点就结束//把孩子的下标赋值给父亲parent child;//假设左孩子最小child parent * 2 1;}else{break;}}
}
建堆
将一个任意序列看成是对应的完全二叉树由于叶结点可以视为单元素的堆因而可以反复利用向下调整建堆法自底向上逐层把所有子树调整为堆直到将整个完全二叉树调整为堆。
可以证明上述完全二叉树中最后一个非叶结点位于第⌊n/2⌋个位置n为二叉树结点目。因此向下调整建堆法需从第⌊n/2⌋个结点开始逐层向上倒退直到根结点。
实现
//交换数据
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{//1.选出左右孩子中小的那一个int child parent * 2 1;//假设左孩子最小while (child size){//当右孩子存在且右孩子小于左孩子if (child 1 size a[child 1] a[child])//大堆a[child1]a[child]{child;//则将右孩子置为child}//2.小的孩子跟父亲比较如果比父亲小则交换然后继续往下调整如果比父亲大则调整结束if (a[child] a[parent])//大堆a[child]a[parent]{//交换数据Swap(a[child], a[parent]);//3.继续往下调最多调整到叶子结点就结束//把孩子的下标赋值给父亲parent child;//假设左孩子最小child parent * 2 1;}else{break;}}
}void HeapSort(int* a, int n)
{//建堆//建堆方式二向下调整//向下调整算法的左右子树必须是堆因此不能使用该方法直接建堆//时间复杂度O(N)//首先将数组中的元素以完全二叉树的形式排列好然后从倒数第一个非叶子结点开始依次向下调整for (int i (n - 1 - 1) / 2; i 0; i--)//n-1为最后一个结点的下标求最后一个结点的父结点的下标(n-1-1)/2{AdjustDown(a, n, i);}
}int main()
{int a[] { 27,15,19,18,28,34,65,49,25,37 };HeapSort(a, sizeof(a) / sizeof(a[0]));return 0;
}
排序
具体步骤如下
将待排序记录按照堆的定义建初堆并输出堆顶元素调整剩余的记录序列利用向下调整建堆法将前n-i个元素重新筛选建成为一个新堆再输出堆顶元素重复执行步骤2进行n-1次筛选新筛选成的堆会越来越小而新堆后面的有序关键字会越来越多最后使待排序记录序列成为一个有序的序列这个过程称为堆排序。
实现
//交换数据
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{//1.选出左右孩子中小的那一个int child parent * 2 1;//假设左孩子最小while (child size){//当右孩子存在且右孩子小于左孩子if (child 1 size a[child 1] a[child])//大堆a[child1]a[child]{child;//则将右孩子置为child}//2.小的孩子跟父亲比较如果比父亲小则交换然后继续往下调整如果比父亲大则调整结束if (a[child] a[parent])//大堆a[child]a[parent]{//交换数据Swap(a[child], a[parent]);//3.继续往下调最多调整到叶子结点就结束//把孩子的下标赋值给父亲parent child;//假设左孩子最小child parent * 2 1;}else{break;}}
}void HeapSort(int* a, int n)
{//建堆//建堆方式二向下调整//向下调整算法的左右子树必须是堆因此不能使用该方法直接建堆//时间复杂度O(N)//首先将数组中的元素以完全二叉树的形式排列好然后从倒数第一个非叶子结点开始依次向下调整for (int i (n - 1 - 1) / 2; i 0; i--)//n-1为最后一个结点的下标求最后一个结点的父结点的下标(n-1-1)/2{AdjustDown(a, n, i);}//排序//时间复杂度O(N*logN)其中N为元素个数logN为向上调整的次数也即树的高度int end n - 1;while (end 0){//将第一个结点与最后一个结点交换Swap(a[0], a[end]);//向下调整选出次大的数AdjustDown(a, end, 0);--end;}
}int main()
{int a[] { 27,15,19,18,28,34,65,49,25,37 };HeapSort(a, sizeof(a) / sizeof(a[0]));return 0;
}
运行结果 算法分析
空间复杂度O(1)。只需要定义几个所需空间为常数级的辅助变量(如i,j,tmp,a[0])与问题的规模n无关。
时间复杂度
建堆时间复杂度
因为堆是一棵完全二叉树而满二叉树又是一种特殊的完全二叉树为了简化计算我们不妨假设此处的堆是一棵满二叉树。 由上图得对于高度为h的满二叉树构成的堆最多进行向上调整的次数设为有 综上证得向上调整建堆的时间复杂度为O(N)。
排序时间复杂度
n个结点的完全二叉树的深度为⌊log2(n)⌋1n个结点排序时调用向下调整函数n-1次总共进行的比较次数不超过2(⌊log2(n-1)⌋⌊log2(n-2)⌋...⌊log2(2)⌋)2n⌊log2(n)⌋因此堆排序在最坏情况下其时间复杂度也为O(N*log2N)这是堆排序的最大优点。
所以堆排序的总的时间复杂度为O(N*log2N)
稳定性不稳定。例如有待排序序列{5,5,3}采用堆排序第一次排序得{3,5,5}说明希尔排序法是不稳定的排序方法。
四.交换排序
所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。交换排 序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
4.1.冒泡排序
冒泡排序是一种简单的交换类排序方法它是通过对相邻的数据元素进行交换逐步将待排序序列变成有序序列的过程。
具体过程反复扫描待排序记录序列在扫描的过程中顺次比较相邻的两个元素的大小若逆序就交换位置。
以升序为例在第一趟冒泡排序中从第一个记录开始扫描整个待排序记录序列若相邻的 两个记录逆序则交换位置。 在扫描的过程中不断地将相邻两个记录中关键字大的记录向后移动最后必然将待排序记录序列中的最大关键字记录换到待排序记录序列的末尾这也是最大关键字记录应在的位置。 然后进行第二趟冒泡排序对前n-1个记录进行同样的操作其结果是使次大的记录被放在第n-1个记录的位置上。 然后进行第三趟冒泡排序对前n-2个记录进行同样的操作其结果是使第三大的记录被放在第n-2个记录的位置上。 如此反复每一趟冒泡排序都将一个记录排到位直到剩下一个最小的记录。 若在某一趟冒泡排序过程中没有发现一个逆序,则可直接结束整个排序过程所以冒泡过程最多进行n-1趟。
实现
void BubbleSort(int* a, int n)
{//判空assert(a);//排升序for (int j 0; j n - 1; j){//用于判断是否有数据发生交换int exchange 0;for (int i 1; i n - j; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);//若有数据发生交换则将exchange置为1exchange 1;}}//若本趟没有数据发生交换则说明数组已经有序直接退出if (exchange 0){break;}}
}
注意
在排序的过程中从某一轮开始数组已经变得有序但是循环还在继续显然后面的排序都是无用功。为了避免这些时间的消耗只需在算法中设置一个简单的标志位exchange即可。使用该排序算法能明显降低时间损耗。而在空间上只是多用了一个int型的变量exchange空间复杂度仍为一个常数。
运行结果 算法分析
空间复杂度O(1)。只需要定义几个所需空间为常数级的辅助变量(如i,j,tmp,a[0])与问题的规模n无关。
时间复杂度最好的情况是初始序列已经满足要求的排序序列此时时间复杂度为O(N)最坏的情况是初始序列刚好为要求顺序的逆序此时的时间复杂度为。
设待排序的数据元素个数为N总共要进行N-1趟冒泡排序第一趟冒泡排序最多进行N-1次数据交换第二趟冒泡排序最多进行N-2次数据交换..最后一趟冒泡排序最多进行1次数据交换因此总共要进行数据交换的次数为 根据大O渐进法规则冒泡排序的时间复杂度为。
稳定性稳定。冒泡排序不会改变两个键值相同记录的先后顺序因为并不满足循环判断条件所以无法对它们进行位置交换。因此冒泡排序是稳定的。
4.2.快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
快速排序的递归实现
法一hoara法
选出一个key一般选择最左边或者最右边的值单趟排完之后要求左边比key要小右边比key要大。具体步骤右边先走R从右向左找遇到比key小的值就停下L从左向右找遇到比key大的值就停下然后进行交换重复上述操作若相遇则停下。
注意L和R指针并不是同时运动的而是有一定的先后顺序。
如果选取最左边的元素作为key则R先向左运动。如果选择最右边的元素作为key在L先向右运动。
为什么选择最左边的值做key时要让右边先走 答因为要保证相遇位置的值比key要小或者就是key的位置。
情况一R先走R停下来L去遇到了R相遇的位置就是R停下来的位置R停的位置就是比key要小的位置情况二R先走R没有遇到比key要小的值R去遇到了L相遇的位置是L上一轮停下来的位置要么就是key的位置要么比key要小。
建议左边做key让右边先走右边做key让左边先走 实现
void Swap(int* px, int* py)
{int tmp *px;*px *py;*py tmp;
}int PartSort(int* a, int begin, int end)
{int left begin;//让left指向数组起始位置int right end;//让right指向数组末尾位置int keyi left;//将最左边的值选为keywhile (left right){//右边先走//找小while (left right a[right] a[keyi])//要取到号否则会陷入死循环{--right;}//左边再走//找大while (left right a[left] a[keyi]){left;}//R从右向左找遇到比key小的值就停下L从左向右找遇到比key大的值就停下然后进行交换Swap(a[left], a[right]);}//若相遇则将key放到right和left相遇的位置Swap(a[keyi], a[left]);//更新keyi的位置keyi left;return keyi;
}void QuickSort(int* a, int begin, int end)
{//若beginend则递归结束if (begin end){return;}//单趟排序获取key值int key PartSort(a, begin, end); //递归左区间[begin,keyi-1]QuickSort(a, begin, key - 1);//递归右区间[keyi1,end]QuickSort(a, key 1, end);
}
法二挖坑法
先将第一个数据存放在临时变量key中形成一个坑位R开始向前移动找比key的值小的位置找到后将该值放入坑位中该位置形成新的坑位L开始向后移动找比key大的值找到后又将该值放入坑位中再形成新的坑位。R再次向前移动找比key小的位置找到后将该值放入坑位该位置形成新的坑位L紧接着向后移动找到比key小的位置找到后将该值放入坑位该位置形成新的坑位。重复上述操作直到L和R相遇见将key中的值放入坑位。结束循环此时坑位左边的值都比坑位小右边的值都比坑位大。 实现
void Swap(int* px, int* py)
{int tmp *px;*px *py;*py tmp;
}int PartSort(int* a, int begin, int end)
{//将第一个数据保存在变量key中int key a[begin];//先将坑位设置在第一个数据的位置int piti begin;while (begin end){//从右向左找小于key的值并将其填到左边的坑里面去同时这个位置形成新的坑while (begin end a[end] key)//为了防止越界以及避免死循环{--end;}a[piti] a[end];piti end;//从左向右找大于key的值并将其填到右边的坑里面去同时这个位置形成新的坑while (begin end a[begin] key){begin;}a[piti] a[begin];piti begin;}//若相遇且一定相遇在坑的位置上a[piti] key;return piti;
}void QuickSort(int* a, int begin, int end)
{//若beginend则递归结束if (begin end){return;}//单趟排序获取key值int key PartSort(a, begin, end); //递归左区间[begin,keyi-1]QuickSort(a, begin, key - 1);//递归右区间[keyi1,end]QuickSort(a, key 1, end);
}
法三前后指针法
初始时prev指针指向序列开头cur指针指向prev指针的后一个位置然后判断cur指针指向的数据是否小于key若小于则prev指针后移一位并将cur指向的内容与prev指向的内容交换然后cur指针若大于则cur指针继续。当cur指针已经越界这时将prev指向的内容与key进行交换循环结束此时key左边的数据都比key小key右边的数据都比key大。 实现
void Swap(int* px, int* py)
{int tmp *px;*px *py;*py tmp;
}int PartSort(int* a, int begin, int end)
{int pre begin;//prev指针指向序列开头int cur begin 1;//cur指针指向prev指针的后一个位置int keyi begin;//将最左边的值选为keywhile (cur end){//如果cur位置的值小于keyi位置的值if (a[cur] a[keyi] pre ! cur)//若pre之后指向与cur同一个位置此时指向的内容相同则不交换{Swap(a[pre], a[cur]);}cur;}//当cur已经越界时Swap(a[pre], a[keyi]);//更新keyikeyi pre;return keyi;
}void QuickSort(int* a, int begin, int end)
{//若beginend则递归结束if (begin end){return;}//单趟排序获取key值int key PartSort(a, begin, end); //递归左区间[begin,keyi-1]QuickSort(a, begin, key - 1);//递归右区间[keyi1,end]QuickSort(a, key 1, end);
}
快速排序优化
三数取中法选key
第一个数中间的数以及最后一个数选一个不是最大也不是最小那一个。
为什么说找出来的mid是最适合做key
答一般选取的key都是数组起始值或者末尾值若此时的key值是最大值或者最小值那么就会造成快速排序性能退化。所以若能找出一个介于最大值与最小值之间的中间值就能大大提高快速排序的性能。 实现
int GetMidIndex(int* a, int begin, int end)
{int mid (begin end) / 2;if (a[begin] a[mid]){if (a[mid] a[end]){return mid;}else if (a[begin] a[end]){return end;}else{return begin;}}else//a[begin] a[mid]{if (a[mid] a[end]){return mid;}else if (a[begin] a[end]){return begin;}else{return end;}}
}
小区间非递归优化
随着递归次数的增加那么程序在递归过程中所消耗的内存也会越来越多当数据量稍微大一些时甚至可能会导致栈溢出。所以为了提高系统的效率我们将递归过程中产生的小区间改用非递归的方式。递归划分小区间当区间较小时就不再采用递归的方式去对这个小区间进行排序而是考虑用其他排序方法比如插入排序对小区间进行处理。假设区间小于10时不再递归排序小区间则可以减少80%以上的递归次数。 这里以前后指针法为例将快速排序进行优化
//直接插入排序
void InSertSort(int* a, int n)
{//[0,end]有序把end1位置的值插入保持有序for (int i 0; i n - 1; i){//单趟排序int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];--end;}else{break;}}//1.break出来也就是tmpa[end]//2.tmp比所有的值都小end--之后变为-1小于0a[end 1] tmp;}
}//数据交换
void Swap(int* px, int* py)
{int tmp *px;*px *py;*py tmp;
}/三数取中法选key
int GetMidIndex(int* a, int begin, int end)
{int mid (begin end) / 2;if (a[begin] a[mid]){if (a[mid] a[end]){return mid;}else if (a[begin] a[end]){return end;}else{return begin;}}else//a[begin] a[mid]{if (a[mid] a[end]){return mid;}else if (a[begin] a[end]){return begin;}else{return end;}}
}//前后指针法
int PartSort(int* a, int begin, int end)
{int pre begin;//prev指针指向序列开头int cur begin 1;//cur指针指向prev指针的后一个位置int keyi begin;//将最左边的值选为keyint midi GetMidIndex(a, begin, end);Swap(a[keyi], a[midi]);while (cur end){//如果cur位置的值小于keyi位置的值if (a[cur] a[keyi] pre ! cur)//若pre之后指向与cur同一个位置此时指向的内容相同则不交换{Swap(a[pre], a[cur]);}cur;}//当cur已经越界时Swap(a[pre], a[keyi]);//更新keyikeyi pre;return keyi;
}//初始化
int callCount 0;//需在头文件进行声明再使用//[begin,end]
void QuickSort(int* a, int begin, int end)
{callCount;//当区间不存在或者只有一个值时则不需要再处理if (begin end){return;}//递归到小的子区间时可以考虑使用插入排序if (end - begin 10){int keyi PartSort(a, begin, end);//[begin,keyi-1] keyi [keyi1,end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);}else{//插入排序InSertSort(a begin, end - begin 1);}
}运行结果 快速排序的非递归实现
如果对大量有序数据或者接近有序的数据进行排序则可能会造成栈溢出。为了避免递归层数太深或让快速排序适用于规模较大且接近有序的数据用非递归的方法实现快排显得尤为重要。
递归大问题极端场景下面如果递归深度太深会出现栈溢出。 解决方法
将递归改成循环比如斐波那契数列归并排序等用数据结构栈模拟递归过程。
思路分析
1.首先将待排序数组的起始元素下标设为begin末尾元素下标设为end则此时的待排序数组转化为[begin,end]。然后让该数组的末尾元素和起始元素分别进栈。接着读取栈顶的两个元素也就是读取数组的起始元素和末尾元素并将它们分别出栈。最后对该数组[begin,end]进行第一次单趟快排找出第一个满足条件的key值。
2.在找出第一个key值之后记录其对应位置为keyi。此时原数组[left,right]被划分为三个部分[left,keyi-1]keyi[keyi1,right]。
3.对划分出来的两个子区间[left,keyi-1]和[keyi1,right]分别进行上述操作即先让右小区间[keyi1,right]入栈再让左小区间[left,keyi-1]入栈然后读取栈顶两个元素并分别出栈同时进行相应的快排操作。
4.重复上述操作当栈为空时则表明排序结束数组已经有序。 实现
void QuickSortNonR(int* a, int begin, int end)
{ST st;//栈后进先出//初始化StackInit(st);//进栈StackPush(st, end);StackPush(st, begin);while (!StackEmpty(st)){int left StackTop(st);StackPop(st);int right StackTop(st);StackPop(st);int keyi PartSort3(a, left, right);//[left,keyi-1] keyi [keyi1,right]//栈里面的区间都会拿出来单趟排序分割子区间再入栈if (left keyi - 1){StackPush(st, keyi - 1);StackPush(st, left);}if (keyi 1 right){StackPush(st, right);StackPush(st, keyi 1);}}//销毁StackDestory(st);
}
运行结果 算法分析
空间复杂度快速排序递归算法的执行过程对应一棵二叉树,理想情况下是一棵完全二叉树递归工作栈的大小与上述递归调用二叉树的深度对应平均情况下辅助空间复杂度为O(logN)。
时间复杂度分析快速排序的时间耗费共需要进行多少趟排序取决于递归调用深度。 快速排序的最好情况是每趟将序列一分两半正好在表中间将表分成两个大小相等的子表类似于折半查找。时间复杂度为O(n*logN)。 快速排序的最坏情况是已经排好序第一趟经过n-1次比较第一个记录定在原位置左部子表为空表右部子表为n-1个记录。第二趟n-1个记录经过n-2次比较第二个记录定在原位置左部子表为空表右部子表为n-2个记录以此类推共需进行n-1趟排序其比较次数为(n-1)(n-2)…1n*(n-1)/2。时间复杂度为O(n^2)。 快速排序的空间复杂度分析快速排序递归算法的执行过程对应一棵二叉树理想情况下是一棵完全二叉树递归工作栈的大小与上述递归调用二叉树的深度对应平均情况下辅助空间复杂度为O(logN)。
稳定性不稳定。如数组{3,3,2}当发生第一次数据交换时原数组变为{2,3,3}。所以快速排序是不稳定的算法。
五.归并排序
归并排序是建立在归并操作上的一种有效的排序算法该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。
二路归并假设初始序列含有n个记录首先将这n个记录看成n个有序的子序列每个子序列的长度为1然后两两归并得到⌈n/2⌉个长度为2(n为奇数时最后一个序列的长度为1)的有序子序列。在此基础上再对长度为2的有序子序列进行两两归并得到若干个长度为4的有序子序列。如此重复直到得到一个长度为n的有序序列为止。 归并排序的递归实现
具体步骤
假设有待排序数组[begin,end]首先判断begin是否小于end若小于则表明数组存在否则直接退出然后将数组从中间mid(beginend)/2分开接着对左半部分子区间[begin,mid]和右半部分子区间[mid1,end]分别递归地进行归并排序让子区间变得有序当子区间变得有序之后再进行归并将左右两个有序子序列归并为一个最后再将归并好的数据拷回原数组。
实现
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end){return;}int mid (begin end) / 2;//分治递归让子区间有序 [begin,mid][mid1,end]//递归左区间_MergeSort(a, begin, mid, tmp);//递归右区间_MergeSort(a, mid 1, end, tmp);//归并 [begin,mid][mid1,end]int begin1 begin;int end1 mid;int begin2 mid 1;int end2 end;int i begin1;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}//当begin1还没走完while (begin1 end1){tmp[i] a[begin1];}//当begin2还没走完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){printf(malloc fail\n);exit(-1);}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}递归分析 运行结果 归并排序的非递归实现
如何对数组进行分解并将分解后的子区间进行排序呢
这里主要是通过控制变量gap来对数组进行分解和归并的。将gap的初始值设为1从数组起始位置开始每次选取两个子区间[i,igap-1]和[igap,i2*gap-1]起始状态的子区间元素个数为1然后将两个子区间进行归并处理。待所有子区间都处理完之后再将gap扩大为原来的2倍从数组起始位置开始每次选取两个子区间[i,igap-1]和[igap,i2*gap-1]起始状态的子区间元素个数为2然后将两个子区间进行归并处理。重复上述操作直到整个数组变得有序。 但是这样进行子区间的划分可能会造成区间越界问题那又该如何处理
我们将两个子区间[i,igap-1]和[igap,i2*gap-1]的边界值分别设为begin1,end1和begin2,end2则子区间转换为[begin1,end1]和[begin2,end2]。可以肯定的是在四个边界值中只有begin1不会发生越界其余三个边界值均有可能发生越界。此时又可分为三种情况进行讨论
end1不越界begin2和end2越界end1、begin2和end2均越界end1和begin2不越界end2越界。
处理方式
法一分析越界的三种情况然后对其分别进行处理也就是将已经发生越界的区间修改为在合理范围内的不存在的区间
法二若end1越界或者begin2越界则可以不归并直接退出循环若只有end2发生越界则直接将已经发生越界的区间修改为在合理范围内的不存在的区间。
实现整个数组归并完之后进行整体拷贝
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){printf(malloc fail\n);exit(-1);}int gap 1;while (gap n){printf(gap%d-, gap);for (int i 0; i n; i 2 * gap){//[i,igap-1][igap,i2*gap-1]//归并 [begin,mid][mid1,end]int begin1 i;int end1 i gap - 1;int begin2 i gap;int end2 i 2 * gap - 1;//越界问题处理-修正边界//注意只有begin1不会越界//若end1越界if (end1 n){end1 n - 1;//begin2和end2已经越界 将[begin2,end2]修正为一个不存在的区间begin2 n;end2 n - 1;}else if (begin2 n)//若begin2越界{//begin2和end2已经越界 将[begin2,end2]修正为一个不存在的区间begin2 n;end2 n - 1;}else if (end2 n)//若end2越界{end2 n - 1;}printf([%d,%d][%d,%d]--, begin1, end1, begin2, end2);int j begin1;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}//当begin1还没走完while (begin1 end1){tmp[j] a[begin1];}//当begin2还没走完while (begin2 end2){tmp[j] a[begin2];}}printf(\n);//把归并数据拷贝回原数组memcpy(a, tmp, sizeof(int) * n);gap * 2;}free(tmp);
}
运行结果 实现归并完一组数据则拷贝一组数据
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){printf(malloc fail\n);exit(-1);}int gap 1;while (gap n){printf(gap%d-, gap);for (int i 0; i n; i 2 * gap){//[i,igap-1][igap,i2*gap-1]//归并 [begin,mid][mid1,end]int begin1 i;int end1 i gap - 1;int begin2 i gap;int end2 i 2 * gap - 1;//end1越界或者begin2越界则可以不归并了if (end1 n || begin2 n){break;}else if (end2 n){end2 n - 1;}printf([%d,%d][%d,%d]--, begin1, end1, begin2, end2);int m end2 - begin1 1;//统计元素个数int j begin1;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}//当begin1还没走完while (begin1 end1){tmp[j] a[begin1];}//当begin2还没走完while (begin2 end2){tmp[j] a[begin2];}//把归并数据拷贝回原数组memcpy(a i, tmp i, sizeof(int) * m);}printf(\n);gap * 2;}free(tmp);
}
运行结果 算法分析
空间复杂度O(N)。在实现归并排序时需要和待排记录等数量的辅助空间因而空间复杂度为O(N)。
时间复杂度O(N*logN)。使用归并排序算法时一趟归并需要将序列中的n个有序小序列进行两两归并并且将结果存放到中间数组tmp[]中这个操作需要扫描序列中的所有记录因此耗费的时间为O(N)。而归并排序过程中的序列分组类似于一棵树所以归并排序需要进行logN次。因为这两种操作是嵌套关系所以归并排序算法的时间复杂度为O(N*logN)。
稳定性归并排序是一种稳定的排序算法。
小结
一般情况下由于要求附加和待排记录等数量的辅助空间因此很少利用二路归并排序进行内部排序归并的思想主要用于外部排序。
六.非比较排序
计数排序是一个非比较排序算法又称为鸽巢原理是对哈希直接定址法的变形应用。其核心在于将输入的数值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序计数排序要求输入的数据必须是有确定范围的整数。
具体操作
找出待排序数组中最大值max和最小值min并新建一个长度为(rangemax-min 1)的数组count统计待排序数组中每个值为i的元素出现的次数并存入数组count的第i项根据每个值为i的元素出现的次数将对应的元素回写到原数组。 实现
void CountSort(int* a, int n)
{int min a[0], max a[0];//寻找数组中的最大值和最小值for (int i 0; i n; i){if (a[i] min){min a[i];}if (a[i] max){max a[i];}}//开辟一个统计次数的数组int range max - min 1;int* count (int*)malloc(sizeof(int) * range);if (count NULL){printf(malloc fail\n);exit(-1);}//将数组初始化为0memset(count, 0, sizeof(int) * range);//统计次数for (int i 0; i n; i){count[a[i] - min];}//回写排序到原数组int j 0;for (int i 0; i range; i){//出现几次就回写几个iminwhile (count[i]--){a[j] i min;}}
} 运行结果 局限性
1.如果是浮点数字符串则不可以 2.如果数据范围很大空间复杂度就会很高则相对不适合。比较适合范围集中且重复数据多。
算法分析
假设要对含有N个元素的数组进行排序range为数组的最大值与最小值之差1count用于记录待排序数组中各个元素出现的次数。
空间复杂度O(range)。计数排序只需要一个大小为range的辅助空间用于统计各个元素所出现的次数。
时间复杂度O(max(Nrange))。当range N也就是当待排序数组的元素较为集中时对应的时间复杂度为O(N)当range N也就是当待排序数组的元素较为分散时对应的时间复杂度为O(range)。
稳定性稳定。计数排序并不会改变相同元素在待排序数组中的先后顺序因为它不涉及元素间的交换。
