网站建设 网络推广,广州市设计院官网,wordpress阿里秀模板,福州网红餐厅本篇文章介绍数据结构中的几种排序哦~ 文章目录 前言一、排序是什么#xff1f;二、排序的分类 1.直接插入排序2.希尔排序3.选择排序4.冒泡排序5.快速排序6.归并排序总结 前言 排序在我们的生活当中无处不在#xff0c;当然#xff0c;它在计算机程序当中也是一种很重要的操… 本篇文章介绍数据结构中的几种排序哦~ 文章目录 前言一、排序是什么二、排序的分类 1.直接插入排序2.希尔排序3.选择排序4.冒泡排序5.快速排序6.归并排序总结 前言 排序在我们的生活当中无处不在当然它在计算机程序当中也是一种很重要的操作排序的主要目的是为了便于查找。
一、排序是什么
所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的一种擦作。
二、排序的分类
框架图 这里呢我们就介绍几种比较重要的排序算法。
1.直接插入排序
扑克牌是我们几乎每个人都可能玩过的游戏吧最基本的扑克玩法大多都是一边摸牌一边理牌的。
这里先看个动图吧你是否看完动图就已经知道这种排序方式的思路了呢
动态图演示 思路 直接插入排序的思路呢就是每次将一个等待排序的元素与已经排序的元素进行一一比较直到找到合适的位置按大小插入。它的基本操作就是将一个记录插入到已经排好序的有序表中从而得到一个新的记录数增1的有序表。
代码如下 //插入排序
#includestdio.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[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];}else{break;}--end;}a[end 1] tmp;}
}//测试
void TestInsertSort()
{int a[] { 9,1,5,7,4,8,3 };InsertSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}
void TestOP()
{srand(time(0));const int N 10000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);for (int i N - 1;i 0;--i){a1[i] rand();a2[i] a1[i];}int begin1 clock();InsertSort(a1, N);int end1 clock();printf(InsertSort:%d\n, end1 - begin1);free(a1);free(a2);
}
int main()
{TestOP();TestInsertSort();return 0;
} 执行结果 2.希尔排序缩小增量排序
首先给大家说明一下希尔排序是D.L.Shell于1959年提出来的一种排序算法在这之前呢排序算法的时间复杂度大多基本都是O(n^2)的而希尔排序算法可以说是突破这个时间复杂度的第一批算法之一了换句话说希尔排序算法的发明使得我们终于突破了慢速排序的时代。之后更为高效的排序算法也就相继出现了。
有条件了很好没条件我们去创造条件也是可以去做的那么在科学家希尔对直接插入排序进行打磨之后就可以增加效率了。一个问题的解决务必是因为该问题的诞生那如何让待排序的记录个数变少呢分割成若干个子序列此时每个序列待排序的记录个数就比较少了接着在这些子序列内分别进行直接插入排序当整个序列都基本有序时这里可要注意啦是基本有序时再次对全体记录进行一次直接插入排序。 强调一下这里的基本有序指的是小的关键字基本在前边大的关键字基本在后边不大不小的基本在中间。就和我们高中跑早操排队一样嘛但是偶尔会出现一两对身高不太一样的好朋友往一块站对嘛。 可是这里分割待排序记录的目的是减少待排序记录的个数并且使整个序列向基本有序发展·不过按照这样的方式好像并不能满足我们让分完组后就各自排序的这种要求哦所以我们需要采取的措施是将相距某个“增量”的记录组成一个子序列这样的话才能够保证在子序列内部分别进行直接插入排序后得到的结果是基本有序而不是局部有序的。 总结希尔排序的基本思想就是先选定一个整数把待排序文件中所有记录分成gap组所有距离为gap的记录在同一组内并且对每一组内的记录进行排序。然后重复上述分组和排序的工作。当达到gap 1时所有记录在同一组内排好序。
代码如下 //希尔排序
void PrintArray(int* a, int n)
{for (int i 0;i n;i){printf(%d, a[i]);}printf(\n);
}void ShellSort(int* a, int n)
{int gap n;while (gap 1){gap gap / 3 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 end - gap;}else{break;}}a[end gap] tmp;}}
}
//测试
void TestShellSort()
{int a[] { 9,1,5,7,4,8,3 };ShellSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}
void TestOP()
{srand(time(0));const int N 10000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);for (int i N - 1;i 0;--i){a1[i] rand();a2[i] a1[i];}int begin1 clock();ShellSort(a1, N);int end1 clock();printf(ShellSort:%d\n, end1 - begin1);free(a1);free(a2);
}
int main()
{TestOP();TestShellSort();return 0;
} 执行结果; 希尔排序的特性总结
1当gap 1时其实都是预排序目的是让数组更接近于有序。 当gap 1 时其实就是直接插入排序数组已经接近有序了这样就会很快。就整体而言可以达到优化的效果。
2希尔排序的时间复杂度不是很好计算因为gap的取值方法很多导致很难去计算。 说明gap的取法有很多种Shell提出取 gap n / 2, gap gap / 2,直到gap为1 后来Knuth提出取gap (gap / 3) 1。 无论哪一种都没有得到证明 注在Knuth所著的《计算机程序设计技巧》第三卷中利用大量的实验统计资料得出当n很大时关键码平均比较次数和对象平均移动次数在n^1.25~1.6*n^1.25范围内这是在利用直接插入排序作为子序列排序方法的情况下得到的。 3.选择排序
动态图演示 看完图有没有思路呢其实选择排序的思路蛮简单的就是每一次从待排序的数据元素中选出最小/最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完。这种排序也就是通过n-i次关键字间的比较从n - i 1个记录中选出关键字最小的记录并且和第 i (1 i n)个记录交换。
代码如下 //选择排序
void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int mini begin, maxi begin;for (int i begin 1; i end; i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}Swap(a[begin], a[mini]);if (maxi begin){maxi mini;}Swap(a[end], a[maxi]);begin;--end;}
}//测试
void TestSelectSort()
{int a[] { 9,1,5,7,4,8,3 };SelectSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestOP()
{srand(time(0));const int N 100;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);for (int i N - 1; i 0; --i){a1[i] rand();a2[i] a1[i];}int begin1 clock();SelectSort(a1, N);int end1 clock();printf(SelectSort:%d\n, end1 - begin1);free(a1);free(a2);
}
int main()
{TestOP();TestSelectSort();return 0;
}执行结果 从选择排序的过程来看它最大的特点就是交换移动数据次数相对较少这样也就节约了相应的时间。
总结选择排序它的思路很好理解但是其效率并不是很好很少用到。
4.冒泡排序
无论你学习哪种编程语言在学到循环和数组的时候通常都会介绍一种排序算法而这个算法一般就是冒泡排序。并不是说它的名字好听而是说这个算法的思路最简单最容易理解哦。
冒泡排序呢我们可以理解为一种交换排序其基本思想是对数组进行遍历每次对相邻两个进行比较大小如果大的数值在前面那么交换位置也可以理解为升序完成一趟遍历后数组中最大的数值到了数组的末尾位置再对前面n-1个数值进行相同的遍历一共完成n-1次遍历就实现了排序完成。
动态图演示 代码如下 //冒泡排序
void PrintArray(int* a, int n)
{for (int i 0;i n;i){printf(%d, a[i]);}printf(\n);
}
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}
void BubbleSort(int* a, int n)
{for (int j 0; j n; 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 1;}}if (exchange 0){break;}}
}//测试
void TestBubbleSort()
{int a[] { 9,1,5,7,4,8,3 };BubbleSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}
void TestOP()
{srand(time(0));const int N 100;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);for (int i N - 1; i 0; --i){a1[i] rand();a2[i] a1[i];}int begin1 clock();BubbleSort(a1, N);int end1 clock();printf(BubbleSort:%d\n, end1 - begin1);free(a1);free(a2);
}
int main()
{TestOP();TestBubbleSort();return 0;
} 执行结果 在这里呢简单提一下冒泡排序的效率冒泡排序是稳定的排序算法在相同数据排序时不会影响原来的顺序对结构体类型有影响的。它的时间复杂度是O(n^2),空间复杂度是O(1)。 5.快速排序 终于我们的高手就要出场啦假如说未来你在工作后你的老板让你写个排序算法而你会的算法中竟然没有快速排序那么我建议你还是火速把快速排序算法找来敲入你排序算法的大队伍中吧哈哈哈哈…… 简单介绍一下快速排序吧快速排序算法最早是由图灵奖获得者Tony Hoare设计出来的。他在形式化方法理论以及ALGOL60编程语言的发明中都有卓越的贡献是上世纪最伟大的计算机科学家之一。而这快速排序算法只是他众多贡献中小小的一个发明而已。你们知道吗我们接下来要学习的这个快速排序算法可是被列为20世纪十大算法之一的哦~ 这段话大家好好看看哦~ 希尔排序可以说是直接插入排序的升级都属于插入排序这一大类哦 快速排序可以说是冒泡排序的升级都属于交换排序这一大类哦。也就是通过不断比较和移动交换来实现排序不过它的实现相较其他而言就是增大了记录的比较和移动的距离将关键字大的记录从前面直接移动到后面去关键字较小的记录从后面直接移动到前面从而减少了总的比较次数和移动交换次数。 基本思想任取待排序元素序列中的某个元素作为基准值按照该排序码将待排序码集合分割成两个子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
在这里呢我们主要对hoare排序以及对其的几种优化进行介绍
1hoare版本
hoare版本是快速排序最原始的情况看看单趟的过程
这里单趟的目的是要求左边的key要小右边的key要大
动态图演示 看完图是否稍微有一点点思路呢因为快速排序在排序中很重要所以这里可能会说的详细一点大家不要嫌我啰嗦哦~ 思路: a:先记录下keyi的位置接着 left 和 right 分别从数组两端开始往中间走 b:当right先开始向中间行动如果right处的值小于keyi处所对应的值则停止等待left走 c:此时left开始行动当left找到比keyi处小的值的时候left 和 right处的值进行交换 d:当两个位置相遇时将两个相遇位置的值与keyi处所对应的值进行交换并且将相遇的位置记为新的keyi 代码如下 //这里出现了一种三数取中的方法这样的话快速排序就不会出现最坏情况
// 三数取中void PrintArray(int* a, int n)
{for (int i 0;i n;i){printf(%d, a[i]);}printf(\n);
}
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}
int GetMidi(int* a, int left, int right)
{int mid (left right) / 2;// left mid rightif (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]) // mid是最大值{return left;}else{return right;}}else // a[left] a[mid]{if (a[mid] a[right]){return mid;}else if (a[left] a[right]) // mid是最小{return left;}else{return right;}}
}//快速排序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]);return left;
};
void QuickSort(int* a, int left, int right)
{if (left right)return;if ((right - left 1) 10){int keyi PartSort1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);}else{InsertSort(a left, right - left 1);}
}执行结果 2挖坑法版本
动态图演示 看完图有什么想法吗或许有些同学对快速排序的第一个原始版本中左边设置为keyi之后右边就要先走是不太能理解的吧这里就有脑洞大开的大佬想出了另外一种快速排序的方法可能思路不太一样不过相比而言对我们这些小白来说更容易理解哦~ 思路 a:首先将begin处的值放到key中然后将其设置为坑位接着right抗下任务开始行动找值从而补坑 b:right找到比key小的值后将这个值放到刚才的坑位中然后将这个新的位置重新设置为坑位 c:此时left也开始找值来进行补坑啦找到比key大的值然后将这个值放到坑位中接着将这个新的位置重新设置为坑位 d:当left与right碰面时再将key放入到坑位中 代码如下
//三数取中那一部分在前面哦
//挖坑法int PartSort2(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int key a[left];// 保存key值以后左边形成第一个坑int hole left;while (left right){// 右边先走找小填到左边的坑右边形成新的坑位while (left right a[right] key){--right;}a[hole] a[right];hole right;// 左边再走找大填到右边的坑左边形成新的坑位while (left right a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole
}
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi PartSort2(a, begin, end);// [begin, keyi-1] keyi [keyi1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
} 执行结果 3前后指针法版本
动态图演示 这里呢前后指针法与前面两种版本相比的话无论是从哪个方面考虑都是有很大的提升的也是一种很常见的写法。 思路 a:cur位于begin1的位置prev位于begin的位置keyi先存放begin处的值 b:cur不断往前1直到cur大于等于end时停止循环 c:如果cur处的值小于key处的值而且prev1不等于cur那么与prev处的值进行交换 d:当循环结束时将prev处的值与keyi处的值进行交换而且将其置为新的keyi值 代码如下 //前后指针
int PartSort3(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int prev left;int cur prev 1;int keyi left;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);return prev;
}// [begin, end]
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi PartSort3(a, begin, end);// [begin, keyi-1] keyi [keyi1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}
执行结果 说明 这里在遍历的整个过程中cur是不断向前的只是cur处的值小于keyi处的值时才进行交换使其进行判断在cur位置处的值小于keyi处的值时需要进行判断prev是否等于cur如果等于的话则会出现自己交换自己的情形当然如果相等的话不用进行交换哦~ //这是上面三种情况的测试代码
void TestQuickSort()
{int a[] { 9,1,5,7,4,8,3 };QuickSort(a,0, sizeof(a) / sizeof(int)-1);PrintArray(a, sizeof(a) / sizeof(int));
}void TestOP()
{srand((unsigned)time(0));const int N 1000000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);for (int i N - 1; i 0; --i){a1[i] rand();a2[i] a1[i];}int begin1 clock();QuickSort(a1, 0, N-1);int end1 clock();printf(QuickSort:%d\n, end1 - begin1);free(a1);free(a2);
}
int main()
{TestOP();TestQuickSort();return 0;
} 6.归并排序 归并排序归并归并从字面意思来看我们就可以有着把两个合并到一起的感觉。在数据结构中的定义呢是将两个或两个以上的有序表组合成一个新的有序表。 我想问一下大家知道我们高考完那个所谓的一本二本还有专科线是怎么划分出来的吗简而言之假设各个高校的本科专业要在甘肃省高三学理科的学生中打算招收一万名学生那么将全省参加高考的理科生进行一个倒排序那么这位排名在一万名的这位幸运同学的分数就会是本科线。换个思路想如果你是年级第一但你的分数没有高于这个分数线那么很遗憾你也就失去了上本科的机会。换言之所谓的排名其实也就是这个省份中的每个市一直到每个县城的每个学校的每个班级的排名合并之后从而得到的。
为了让大家更清楚的理解思路这里给大家看个动态图吧~
动态图演示 看完动态图有没有稍微理解一点呢话说回来这就是我们要说的归并排序。
归并排序用到了分治的思想借助递归的方式对一串数字进行排序整个过程分为分开和合并这两个过程其实这里的思想也没有那么难理解就是在代码实现的过程中我们需要写两个函数分别实现分开合并以及每一次排序的这个过程。
通过上面的动图演示我们不难发现首先是要将整个待排序的数逐步分成小块然后再进行归并。 思路 归并排序的思路就是对于左右子区间都有序的序列通过借助一个临时数组进行归并。 然后定义两个指针begin1和begin2分别指向两个子区间的头部另外定义两个指针end1和end2,分别指向两个子区间的尾部。然后依次挨个比较begin1和begin2指向的值将小的放入下面的临时数组中直到其中的一个区间遍历完成后我们就停下来然后接着将没有走完的那个区间剩下的值直接拷贝给新数组。 看到这的时候我们应该能知道当区间里只有1个数的时候那么我们就可以理解为有序了也就是可以进行归并操作了。所以当左右这两个子区间都没有序的时候我们就分治递归不断的分割区间直到区间分割到只剩下1个数的时候此时我们就进行归并啦~
代码实现
//sort.c
#includeSort.h
#includeStack.h
#includestdlib.hvoid PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}归并排序递归实现
void _MergeSort(int* a, int* tmp, int begin, int end)
{if (end begin)return;int mid (end begin) / 2;_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid 1, end);int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int index begin;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 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 fail);return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);
} 我们常说没有最好只有更好。虽然说归并排序大量引用了递归尽管在代码上是比较清晰的可以使我们容易理解但是这会造成时间和空间上的性能损耗我们排序追求的不就是效率吗有没有可能将递归转化为迭代呢当然可以而且改进之后性能上可是进一步提高了哦~
前面提到的是归并排序的递归思想那接下来就说一下归并排序的非递归是怎么样的。 思路 a:申请空间使它的大小为两个已经排序的序列的和然后该空间用来存放合并后的序列 b设定两个指针最开始的两个位置分别为两个已经排序的序列的起始位置 c:比较两个指针所指向的元素选择相对小的元素放入到合并的空间中并且移动指针到下一个位置 d:对上一步的步骤进行重复直到某一指针超出序列尾部将另一个序列剩下的所有元素怒直接复制到合并的序列尾部。 代码实现
//sort.c
void TestMergeNonRSort()
{int a[] { 9,1,2,5,7,4,3,9,3,1,2 };MergeSortNonR(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestOP()
{srand(time(0));const int N 10000000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);for (int i N - 1; i 0; --i){a1[i] rand() i;a2[i] a1[i];}int begin1 clock();MergeSortNonR(a1, N);int end1 clock();printf(MergeSortNonR:%d\n, end1 - begin1);free(a1);free(a2);
}int main()
{//TestOP();TestMergeNonRSort();return 0;
} 说明非递归的方法虽然说不是很好理解也有点难但是其避免了递归时深度为log2n的栈空间并且避免递归也在时间性能上有一定的提升可以说使用归并排序时尽可能考虑用非递归的方法。
7.计数排序
这里要说的计数排序呢它的原理就是通过遍历数组记录每一个数字出现的次数最终在新数组中体现出来那么是如何实现的呢 思路 a:首先我们先遍历整个数组找到数组中数值最大的数字max,并且申请max1个桶随便起的名字哈来存储每个数字出现的次数此时用下表记录 b:然后我们遍历原来的数组找到每个数字对应的桶号并且计数 c:遍历桶数组看对应的桶内计数是多少那么就取出几个下标值放到原数组中。 代码实现
//sort.c
//计数排序
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);printf(range:%d\n,range);if (count NULL){perror(malloc fail);return;}memset(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){while (count[i]--){a[j] i min;}}
}
运行结果和前面的一样就不贴出来啦大家主要要体会每种排序的精髓在哪完全理解它的思路要领核心还有它之所以叫这个排序是为什么到底哪里和其他的排序方式有差别我想如果大家报着这个态度去学习每一种排序那数据结构中的几种排序不得被你狠狠拿捏了……
总结
这里呢就对几种排序的时间复杂度空间复杂度进行一个简单的总结哦~ 图片贴到这里啦大家格外要理解稳定性不稳的几种排序的理由哦~
好啦关于数据结构中几种常见排序就先介绍到这里啦如果哪里出错了欢迎大家留言和我一起进步嘞。
