阅读量:1
文章目录
前言
数组是一组有序数据的集合。这里的“有序”指的是数组元素在内存中的存放方式是有序的，其引用方式有规律可循，而不是说数组元素在数组中是按照数值大小有序排列的。那么有没有什么办法让数组元素按照数值大小有序排列呢？接下来，给大家分享一下数组的各种常用的五种排序算法。
数组常用的五种排序方式：
选择排序、冒泡排序、交换排序、插入排序、折半排序
注：本章内容实例均以从小到大排序为准，从大到小排序原理相同。聪明的你看完本章后学会原理，解决大到小排序问题不在话下！
一、选择排序
1.1 原理
选择排序原理：每次在待排序的数组中，查找最小值，与所在的数组中的第一个位置交换元素，下一次排序时，从第二个位置开始向后查找，以此类推。
我们拿到一个数组，第一次排序，在数组中找到最小值1，和查找数组的第1个位置的元素数据8互换，将元素1放在数组下标0的位置上。第一次排序后数组的顺序是1，5，10，3，8；第二次排序在【5，10，3，8】数组中查找到最小值3，和当前查找数组的第一个位置的元素5交换位置，得到排序后的顺序1，3，10，5，8；第三次在【10，5，8】中查找到最小值5，和当前查找数组的第一个位置互换，得到排序后的顺序1，3，5，10，8；第四次排序在【10，8】中查找到最小值8，和当前查找数组的第一个位置互换，得到排序后的顺序1，3，5，8，10。至此完成从小到大的排序。
1.2 代码实现
int arr[10] = {15,6,20,13,16,8,2,18,7,10}; int pos,min;//min表示最小数组元素，pos表示最小数组元素的下标 for (int i = 0; i < 10; i++) {//设置外层循环下标为0~9 min = arr[i];//假设当前元素为最小值 pos = i;//记录下标 for (int j = i+1; j < 10; j++) {//设置内层循环下标为i+1~9，表示剩下的未排序数组元素部分 if (min > arr[j]) {//重新修正最小值 min = arr[j]; pos = j; } } arr[pos] = arr[i];//将最小元素和当先排序数组对应的元素交换位置 arr[i] = min; } for (int i = 0; i < 10; i++) { printf("%d ", arr[i]); } （1）设定一个数组，当然可以写成scanf形式让用户自己输入，这里为了简洁我们将其写死。定义min和pos，min表示最小数组元素，pos表示最小数组元素的下标。
（2）设置一个嵌套循环，外层循环下标从0-9，在每次循环时将对应当前次数的数组元素设置为最小值，也就是说，如果当前循环是第3次，那么就将数组中的第三个元素设置为最小值。在内存循环中，设置内层循环下标为i+1~9，表示剩下的未排序数组元素部分，循环比较查找出未排序数组元素的最小值，当内层循环结束时，将最小值与数组下标为i的元素互换。
（3）当外层循环结束时，代表数组排序完成。
二、冒泡排序
2.1 原理
冒泡排序原理：依次比较数组中相邻的元素，每次都将较小的数排在较大的数的前面，实现数组元素的从小到大排序。
在每一次循环中，第一次交换，先比较第一和第二个元素大小，如果第一个元素比第二个元素大，则交换两个元素，否则保持当前位置不交换实例中8大于5，交换两个元素位置得到数组【5，8，10，3，1】；第二次交换，比较数组第二个和第三个元素大小，8小于10，保持当前位置；第三次交换，比较数组第三个和第四个元素大小，10大于3，交换位置，得到数组【5，8，3，10，1】；第四次交换，比较数组第四个和第五个元素大小，10大于1，交换位置，得到数组【5，8，3，1，10】，完成第一次循环。当执行完全部循环后，得到一个从小到大的数组。
这里大家要注意不要弄混一次循环和一次交换，一次循环中包含多次元素交换。
2.2 代码实现
int arr[10] = {15,6,20,13,16,8,2,18,7,10}; int i, j; int temp; int flag = 1;//结束冒牌排序的标志 while (flag) { flag = 0;//如果本次冒泡排序没有进入进入到if语句内，则代表排序完成 for (i = 0; i < 9; i++) {//对数组中的每个相邻的元素进行大小比较 if (arr[i] > arr[i + 1]) {//如果前面一个比后一个大，则进行交换 flag = 1;//将标志位置成1， temp = arr[i + 1];//交换两个数据 arr[i + 1] = arr[i]; arr[i] = temp; } } } for (int i = 0; i < 10; i++) { printf("%d ", arr[i]); } （1）首先定义一个flag，用于我们结束循环的检测标志。
（2）因为我们不知道要进行几次冒泡排序，可以写一个while循环，循环内部，我们先将flag标志置成0，当本次循环内没有将flag置成1的操 作（也即是没有进入到后面的if语句中），证明数组内的相邻元素，后一个都比前一个大，排序完成结束循环。
（3）for循环内对数组中的每一组相邻的元素进行比较，如果前面元素比后面的大，则交换两个元素，并且将flag置为一，表示不结束while需缴纳换，直到9次for循环中都没有进入if语句中，排序完成结束循环。
三、交换排序
3.1 原理
交换排序原理：将每一位数与其后的所有数一一比较，如果发现符合条件的元素，则交换数据。
在第一次排序中，第一次交换，将第一个数字8和后面的每一个数字进行比较。首先比较8和5，8比5大，交换两个数的位置，此时5成为第一个元素；
第二次交换中，将5和10比较，5小于10，保持当前位置；
第三次交换中，将5和3比较，5大于3，交换两个数的位置，此时3成为第一个元素；
第四次交换中，将3和1比较，3大于1，交换两个数的位置，完成第一次排序，得到数组1，8，10，5，3。
第二次排序从第二个元素8开始，原理相同这里不再赘述。
3.2 代码实现
int main() { int arr[10] = { 15,6,20,13,16,8,2,18,7,10 }; int i, j; int temp,pos; for (i = 0; i < 9; i++) {//外循环，表示每次排序中第一个元素的位置 for (j = i + 1; j < 10; j++) {//内循环，表示后面待比较的元素 if (arr[i] > arr[j]) {//第一个元素比当前元素大，则交换两者位置 temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } for (int i = 0; i < 10; i++) { printf("%d ", arr[i]); } return 0; } （1）第一个for循环也就是外循环，表示的是每次排序中第一个元素的位置，也表示交换排序需要排序的次数。
（2）第二个for循环也就是内循环，表示后面待比较的元素，如果第一个元素比当前元素大，则交换两者位置。
（3）所有循环结束代表排序完成。
四、插入排序
4.1 原理
插入排序原理：抽出一个数据，在前面的数据中寻找相应的位置插入，然后继续下一个数据，直到完成排序。
第一次排序中，将元素8取出来放在第一个位置。第二次排序，取出第二个元素5，然后和前一个元素比较大小，如果小于前一个元素，则将该元素排在前一个元素的前面，示例中5小于8，所以将5放到8的前面；第三次排序，取出第三个元素10，和前一个元素8比较，10大于8，保持不变；第四次排序，取出第四个元素3，和前一个元素10比较，3小于10，将其排到10的前面，再和8比较，3小于8.排到8的前面，在和5比较，3小于5，排到5的前面；第五次排序，取出第5个元素1，和前一个元素10比较，1小于10，将其排到10的前面，再和8比较，1小于8.排到8的前面，再和5比较，1小于5，排到5的前面，再和3比较，1小于3，排到3的前面，最终得到排序后的数组1，3，5，8，10。
4.2 代码实现
int main() { int arr[10] = { 15,6,20,13,16,8,2,18,7,10 }; int pos, temp; int i, j; for (i = 0; i < 10; i++) { temp = arr[i];//temp记录当前要插入的值 pos = i-1;//插入值的前一个位置 while ((pos >= 0) && (temp < arr[pos])) {//当插入的元素小于前面的元素，并且要插入的值不是第一个元素 arr[pos + 1] = arr[pos];//插入数组 pos--;//继续向前比较 } arr[pos + 1] = temp;//当插入的元素大于前面的元素，将这个位置设置为插入的值 } for (int i = 0; i < 10; i++) { printf("%d ", arr[i]); } return 0; } （1）首先temp=arr[i]，用temp记录当前要插入的值。pos用于记录插入值的前一个位置，便于后面比较大小。
（2）因为pos=i-1，while循环pos>=0判断当前要比较的值必须不是第一个元素，否则会出现数组越界。判断条件temp<arr[pos] 表示当前的要插入的元素小于前一个元素，arr[pos+1] = arr[pos]的意思是，将第pos+1的元素的值设置成前一个元素的值。pos–继续向前比较。
（3）当前位置是数组的第一个元素或者插入的元素大于前一个值时，将当前位置的元素值设置为要插入的值。
还懵？代码跑一下看看
第一次排序，temp等于15，pos等于-1，while判断为false，arr[0](也就是代码中的arr[ pos + 1 ])等于15，第一次排序什么都没变。
第二次排序，temp等于6，pos等于0，while判断为true，进入while循环内，让arr[1]等于arr[0]，也就是arr[1]等于15，此时数组为
【15，15，20,13,16,8,2,18,7,10】，pos–等于-1，再次判断while循环为false，不进入while循环内，继续向下执行arr[pos + 1] = temp，arr[0]等于之前记录的temp的值6，完成第二次排序，得到数组【6，15，20,13,16,8,2,18,7,10】。
第三次排序，temp等于20，pos等于1，while判断为false，arr[2]等于temp20，没有改变。得到数组【6，15，20,13,16,8,2,18,7,10】。
第四次排序，temp等于13，pos等于2，while判断为true，进入while循环内，arr[pos + 1] = arr[pos] = =》 arr[3]=arr[2]=20，此时数组为【6，15，20，20,16,8,2,18,7,10】，pos–等于1，while判断temp<arr[1]，13<15，进入while循环内，
arr[pos + 1] = arr[pos] = =》arr[2]=arr[1]=15,此时数组为【6，15，15，20,16,8,2,18,7,10】,pos–等于0，再去判断while循环条件，13<6为false，结束while循环。那么我们要插入的13去哪了呢？接着往下看，arr[pos + 1] = temp，arr[1]=13,这时我们发现，这段代码代表着我们已经成功找到了插入值应该在的位置，我们将这个位置设置为插入的值，得到数组【6，13，15，20,16,8,2,18,7,10】结束本次排序。
剩下的排序跟之前原理相同，这里不再赘述。
五、折半排序
5.1 原理
折半排序又称快速排序，其原理：选择一个中间值（数组中间元素的值），然后把比中间值小的元素放在左边，比中间值大的元素放在右边（具体实现是从两边查找，找到一对后进行交换），然后再对左右两边分别递归完成折半排序。
第一次排序时，我们将中间的元素作为中间值middle，定义low和high分别从两边向中间进行比较。low从下标left(此时left为0)开始从左向右比较，当low指向的元素小于中间值，则继续向后比较，直到low指向的元素大于等于中间值，记录当前low的位置；high从下标right（此时right为元素个数-1）开始从右向左比较，当high指向的元素大于中间值，则继续向前比较，直到high指向的元素小于等于中间值，记录当前high的位置。将low和high元素互换位置，然后给low向右移动一个元素，high向左移动一个元素。当low的位置大于high的位置时，结束本次排序。然后进行左侧递归折半排序，以left（此时为0）作为low的起始位置，right（此时为第一次折半排序结束时high的位置）作为high的起始位置，重复刚才的过程。右侧递归折半排序原理相同。直到将一组数字全部从小到大排序完成。
5.2 代码实现
void Change(int left, int right, int arr[]) { int i, j;//i代表左侧指向位置left，j代表右侧指向位置right int temp; i = left; j = right; int middle = arr[(left + right) / 2];//获取中间值 do { while ((arr[i] < middle) && (i < right)) {//查找左侧比中间值大的元素，记录位置 i++; } while ((arr[j]>middle) && (j>left)) {//查找右侧比中间值小的元素，记录位置 j--; } if (i <=j) {//将记录的左侧和右侧的值互换 temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } while (i<=j);//直到left位置在right的右侧 if (left < j) {//以right为右侧起点，继续递归 Change(left, j, arr); } if (right > i) {//以left为左侧起点，继续递归 Change(i, right, arr); } } int main() { int arr[10] = { 15,6,20,13,16,8,2,18,7,10 }; int pos, temp; int i, j; Change(0, 9, arr); for (int i = 0; i < 10; i++) { printf("%d ", arr[i]); } return 0; } （1）首先给Change（）是折半排序函数，开始时以0为左侧，9为右侧位置。然后获取中间值arr[4]=16，进入do…while循环，查找左侧大于等于中间值的元素，找到20，记录位置i=2；查找右侧小于等于中间值的元素，找到10，记录位置j=9。判断i在j的左侧，交换两者元素，得到数组
【15,6,10,13,16,8,2,18,7,20 】继续执行循环。
（2）左侧继续查找比中间值大的元素，找到16本身，记录当前位置i=4；右侧继续查找比中间值小的元素，找到7，记录当前位置j=8,i在j的左侧，交换两者元素，得到数组【15,6,10,13,7,8,2,18,16,20 】继续执行循环。
（3）左侧继续查找比中间值大的元素，找到18，记录当前位置i=7；右侧继续查找比中间值小的元素，找到18，记录当前位置j=7,交换两者元素，数组不变，i++和j–后，i出现在j的右侧，do…while循环结束，进入左侧递归函数，此时以left（0）为左侧起点，此时的j为右侧起点，继续进行重复操作。
（4）右侧函数递归同理。直到结束完成排序。
总结
这里暂时先介绍五种常用的数组排序方法，其他的排序方法如希尔排序、堆排序等我们放到数据结构模块再跟大家分享。
好了，以上就是关于C语言五种常用的数组排序方法，有什么问题或者文章哪里写的有不对的地方，欢迎评论区或私信告诉我。如果这篇文章对你有帮助的话请点赞收藏关注一下，感谢大家的支持~🌹🌹
