排序算法|两个基本排序算法【选择排序，冒泡排序】【详解】算法|数据结构|c语言|经验分享

文章目录

一、前言
二、选择排序
- 2.1 选择排序（基础版）【必会】
- 2.2 选择排序（优化版）
三、冒泡排序
- 3.1 冒泡排序（基础版）【必会】
- 3.2 冒泡排序（外循环优化版）
- 3.3 冒泡排序（内循环优化版）
四、总结

一、前言??排序法主要分为两种：比较排序和非比较排序。常见的比较排序有：选择排序、冒泡排序、插入排序、归并排序、堆排序、快速排序等。而比较排序是通过两两元素之间的比较来排序的，每个元素都必须和其他元素进行比较才能确定自己的位置。至于常见的非比较排序有：计数排序、基数排序、桶排序等。而非比较排序是通过确定每个元素之前应该有多少个元素来排序的。（这一期只讲解其中的两种排序，其他的留到以后再讲，我会建立一个关于“排序算法”的专栏，以后如果想看其他的排序可以去这个专栏里找）
??相信只要接触过C语言的同学都或多或少了解排序问题，而最基本且最为人所熟知的应该是下面这两种排序：选择排序、冒泡排序（因为这就是基础啊，只要学《C语言》这门课的期末考试就必然会考到）。但我想就算在学校听老师讲过一遍之后，还是会有一些同学对这两种排序的实现模棱两可。下面我会带着大家重新把这两种排序方法走一遍，使你能够透彻的理解这两种算法的原理，能把它们清晰的区分开，并且分别实现这两种排序的算法优化。
二、选择排序
??选择排序是一种简单且直观的排序算法。它的工作原理是：第一趟先从待排序的数据元素种选出最小（或最大）的一个元素，存放在序列的起始位置；然后第二趟再从剩余未查找的元素中寻找最大（或最小）元素放置在该次序列的首位。以此类推，每一趟都可以向前放置一个最小（或最大）元素，直至只剩下两个元素未被排序，这时是不是只需要再进行一趟排序就可以使得整个序列有序。所以从这里我们可以知道：选择排序的趟数是由元素个数来决定的，若现在有n个元素要对其进行排序，那只需要进行n-1趟就好了，如上图所示。
?? 还有一点值得注意的是：在选择排序中，每趟都会选出最大元素与最小元素，然后与两端元素交换。若此时，待排序序列中如果存在与原来两端元素相等的元素，稳定性就可能被破坏。如[5,3,5,2,9]，在array[0]与array[3]元素交换时，序列的稳定性就被破坏了，所以选择排序是一种不稳定的排序算法。
2.1 选择排序（基础版）【必会】??就如面所讲的就是选择排序最基本的算法，下面就举个例子：现有个序列6、7、5、1、4、3、8 ，请将他们进行从小到大依次排序。注意：选择排序是用两层for循环嵌套来实现的，第一层for循是环是对趟数控制，第二层for循环是对比较的次数的控制，而每一趟走下来都能使一个元素找到对应位置，执行（n-1）趟后就可以完成排序，一定记住！！！

文章图片

代码如下：

#includevoid Swap(int* parr, int min, int i) { int tmp = parr[min]; parr[min] = parr[i]; parr[i] = tmp; }void sel_sort(int* parr, int n) { int i = 0; //每一趟都可以确定一个最小数值，然后把其放到该趟的最前面的下标底下。 //下一趟从前一趟的最小值下标后一个下标开始进行 for (i = 0; i < n - 1; i++)//总的比较的趟数 { int j = 0; //先假设前面的元素为最小元素的下标 int min = i; //每趟比较，将前面的元素与其后的元素逐个比较 for (j = i + 1; j < n; j++) { if (parr[j] < parr[min]) { //min变量保存该趟比较过程中，最小元素所对应的数组下标 min = j; } } //交换此次查到的最小值和原最小值 Swap(parr, min, i); } }int main() { int i = 0; int arr[] = { 6,7,5,3,4,1,8 }; int sz = sizeof(arr) / sizeof(arr[0]); //求数组元素个数 sel_sort(arr, sz); //选择排序 for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } }

文章图片

2.2 选择排序（优化版）??选择排序的优化思路一般是在一趟遍历中，同时找出最大值与最小值，放到数组两端，这样就能将遍历的趟数减少一半。过程如下：

文章图片

?? 这样每次找出最大值与最小值放到数组两端后，left和right会靠的越来越近。如果还像上边那样执行（n-1）趟的话left和right必然会交错，但这里完全没有必要执行（n-1）趟，因为把left=right的情况再走一遍。程序如下：

#includevoid Swap(int* arr, int x, int y) { int tmp = arr[x]; arr[x] = arr[y]; arr[y] = tmp; }void sel_sort(int* arr, int num) { int left = 0; int right = num - 1; while (left < right) { //先假设最左侧元素的下标未为最小元素的下标，最右侧元素的下标为最大元素的下标。 int min = left; int max = right; int i = 0; for (i = left; i <= right; i++) { if (arr[i] < arr[min]) { min = i; } if (arr[i] > arr[max]) { max = i; } } //最大值放在最右端 Swap(arr, max, right); //由于上一步把下标（right）和（max）上的数据进行了交换 //所以得考虑最小值（arr[min]）在位置（right）的情况，即：此时的 min = right； if (min == right) { min = max; } //最小值放在最左端 Swap(arr, min, left); //每趟遍历，元素总个数减少2，左右端各减少1，left和right索引分别向内移动1 left++; right--; } }int main() { int i = 0; int arr[] = { 3,5,9,2,4,7 }; int sz = sizeof(arr) / sizeof(arr[0]); //计算数组元素个数 sel_sort(arr, sz); //选择排序 for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } return 0; }

文章图片

三、冒泡排序

文章图片

?? 冒泡排序是比较基础的排序算法之一，其核心思想是相邻的元素两两比较。但与选择排序不同的是，冒泡排序每一趟走下来不仅可以得到一个最大（或最小）的元素，还能使得数列中较大的数下沉，较小的数冒起来。如此走下去，数列必然在n-1趟之前就基本可以做到有序，可见冒泡排序的效率是高于选择排序的。纵观整个排序过程你会发现数列中的元素就如同气泡和水一样，大的下沉小的冒起，所以该排序才会被生动形象的称作冒泡排序，如上图所示。
??值得注意的是：在冒泡排序中，遇到相等的值，是不进行交换的，只有遇到不相等的值才进行交换，所以是稳定的排序方式。
3.1 冒泡排序基础版【必会】【排序算法|两个基本排序算法【选择排序，冒泡排序】【详解】】?? 就如上面所说的冒泡排序每趟会排好一个元素，且使得这次数列中大数下沉小数冒起。排序中将执行n-1趟，每趟会比较n-1次，所以和比较排序一样用两个嵌套的for循环来实现就行了。如下图所示：

文章图片

实现程序如下：

#includevoid bubble_sort(int* arr, int num) { int i = 0; //该循环决定趟数 for (i = 0; i < num - 1; i++) { int j = 0; //该循环决定每趟中元素比较的次数 for (j = 0; j < num - 1 - i; j++) { if (arr[j] > arr[j + 1]) { //交换两元素 int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } }int main() { int i = 0; int arr[] = { 6,7,5,3,4,1,8 }; int sz = sizeof(arr) / sizeof(arr[0]); //计算数组元素的个数 bubble_sort(arr, sz); //冒泡排序 for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } return 0; }

文章图片

3.2 冒泡排序（外循环优化版）??如果逐语句的走一遍冒泡排序案例后，你必然会发现很多时候冒泡排序压根就不需要执行n-1趟，排序有时可能仅仅只需要执行一趟就可以使得整个序列有序，就如下图所示的案例：

文章图片

??那我们该怎么做才能使得排序时不用重复那么多趟呢？也就是说：若整个序列达到了有序但趟数还没有达到n-1趟时，剩下的趟数就被必要执行了。那程序上该怎么改进呢？其实也不难，只需加一个bool变量来判断整个序列是否有序就行，若达到有效就直接退出循环。下面是代码：

#includevoid bubble_sort(int* arr, int num) { int i = 0; //该循环决定趟数 for (i = 0; i < num - 1; i++) { bool flag = true; int j = 0; //该循环决定每趟中元素比较的次数 for (j = 0; j < num - 1 - i; j++) { if (arr[j] > arr[j + 1]) { //交换两元素 int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag = false; } } //判断整个数组是否有序 //若flag=true则表示数组已经有序，否则表示数组还是无序的； if (flag) { break; } } }int main() { int i = 0; int arr[] = { 6,7,5,3,4,1,8 }; int sz = sizeof(arr) / sizeof(arr[0]); //计算数组元素的个数 bubble_sort(arr, sz); //冒泡排序 for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } return 0; }

文章图片

3.3 冒泡排序（内循环优化版）??冒泡排序经过上面的优化后，其实还是存在着一些不必要的比较动作。因为按照现有的逻辑，有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1，第二轮排序过后的有序区长度是2 ……但实际上，数列真正的有序区可能会大于这个长度，比如下图所示的这个前半段无序后半段有序的例子。

文章图片

??如果还是按照上面的方法来排序，那每一趟都必然执行 n-1-i 次的比较，但其实用不到那么多次，因为后面的5、6、7、8已然有序还去比它干神马？这是毫无意义的事。那该如何避免这种情况呢？其实可以在每一趟排序中记录下最后一次元素交换的位置，那个位置也就是无序数列的边界（再往后就是有序区了），然后通过这个位置就避免无意义的比较了。但还是有同学会有质疑：你这举得例子不全面啊，前半段数列里全是要比后半段序列小的元素。如果把上图中的元素3改成9那还能实现该功能吗？当然可以，你可别捡了芝麻丢了西瓜，别死抓着这里数列后半段为有序的这个观点，而忘了冒泡排序的每一趟都可以把一个最大的元素放置到最后！！！
??下面是代码：

#include #includevoid bubble_sort(int* arr, int num) { int i = 0; //该循环决定趟数 for (i = 0; i < num - 1; i++) { bool flag = true; int j = 0; //无序数组的边界，每次比较只需比较到此为止 int border = num - 1; //记录最后一次交换位置 int position = 0; //该循环决定每趟中元素比较的次数 for (j = 0; j < border; j++) { if (arr[j] > arr[j + 1]) { //交换两元素 int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag = false; //把无序数列的边界更新为最后一次交换元素的位置 position = j; } } border = position; //最后的位置就是无序数组的边界 //判断整个数组是否有序 //若flag=true则表示数组已经有序，否则表示数组还是无序的； if (flag) { break; } } }int main() { int i = 0; int arr[] = { 9,3,4,2,1,5,6,7,8 }; int sz = sizeof(arr) / sizeof(arr[0]); //计算数组元素的个数 bubble_sort(arr, sz); //冒泡排序 for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } return 0; }