文章目录
- 前言
- 一、选择排序
- 1.1 原理
- 1.2 代码实现
- 二、冒泡排序
- 2.1 原理
- 2.2 代码实现
- 三、交换排序
- 3.1 原理
- 3.2 代码实现
- 四、插入排序
- 4.1 原理
- 4.2 代码实现
- 五、折半排序
- 5.1 原理
- 5.2 代码实现
- 总结
前言
数组是一组有序数据的集合。这里的“有序”指的是数组元素在内存中的存放方式是有序的，其引用方式有规律可循，而不是说数组元素在数组中是按照数值大小有序排列的。那么有没有什么办法让数组元素按照数值大小有序排列呢？接下来，给大家分享一下数组的各种常用的五种排序算法。
数组常用的五种排序方式：
选择排序、冒泡排序、交换排序、插入排序、折半排序
注：本章内容实例均以从小到大排序为准，从大到小排序原理相同。聪明的你看完本章后学会原理，解决大到小排序问题不在话下！
一、选择排序
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 arr[j]) {//重新修正最小值 min = arr[j]; pos = j; } } arr[pos] = arr[i];//将最小元素和当先排序数组对应的元素交换位置 arr[i] = min; } for (int i = 0; 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 arr[i + 1]) {//如果前面一个比后一个大，则进行交换 flag = 1;//将标志位置成1， temp = arr[i + 1];//交换两个数据 arr[i + 1] = arr[i]; arr[i] = temp; } } } for (int i = 0; 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 arr[j]) {//第一个元素比当前元素大，则交换两者位置 temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } for (int i = 0; i（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 = 0) && (temp（1）首先temp=arr[i]，用temp记录当前要插入的值。pos用于记录插入值的前一个位置，便于后面比较大小。
（2）因为pos=i-1，while循环pos>=0判断当前要比较的值必须不是第一个元素，否则会出现数组越界。判断条件temp （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[pos + 1] = arr[pos] = =》arr[2]=arr[1]=15,此时数组为【6，15，15，20,16,8,2,18,7,10】,pos–等于0，再去判断while循环条件，13 int i, j;//i代表左侧指向位置left，j代表右侧指向位置right int temp; i = left; j = right; int middle = arr[(left + right) / 2];//获取中间值 do { while ((arr[i] left)) {//查找右侧比中间值小的元素，记录位置 j--; } if (i //将记录的左侧和右侧的值互换 temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } while (i//以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
