【数组的排序方法】 选择法、冒泡法、交换法、插入法、折半法

大家好，欢迎来到IT知识分享网。

目录

 前言

一、选择法排序

二、冒泡法排序

三、交换法排序

四、插入法排序

五、折半法排序

 前言

       我们前面已经了解过数组的理论知识，但虽说数组是一个有序的集合，但这里的顺序指的是数组元素所在数组中的位置，我们接下来要说到的就是如何给数组里的数据按照大小顺序来排序。

一、选择法排序

       顾名思义，选择法就是每次选择数组中最大或者最小的数组元素，将这个数组元素的值与前面没有进行排序的数组元素的值互换。

示例程序如下（降序排列）：

#include<stdio.h> int main() { int i, j; int a[10]; int iTemp; int iPos; printf("请输入数组中的元素的值：\n"); for (i = 0; i < 10; i++) { printf("a[%d]=", i); scanf_s("%d", &a[i]); } //排序 for (i = 0; i < 9; i++) { iTemp = a[i]; iPos = i; for (j = i + 1; j < 10; j++) { if (a[j] > iTemp) { iTemp = a[j]; iPos = j; } } a[iPos] = a[i]; a[i] = iTemp; } //输出 for (i = 0; i < 10; i++) { printf("%d ", a[i]); if (i == 4) printf("\n"); } return 0; }

 运行结果如下：

       然后这个选择法的运行逻辑就是先选取第一个数组元素，然后从这个数组元素之后的元素开始挨着与这个元素比较大小，如果大于所选取的数组元素，那就将这个元素的值与开始元素交换，全部运行完之后输出结果。

二、冒泡法排序

       前面的选择法是依次把未排序的最大的数组元素排到开头或末尾，然后冒泡法是设置嵌套循环，进行若干（数组元素个数）次相邻数组元素之间的交换。

#include<stdio.h> int main() { int i, j; int a[10]; int iTemp; int iPos; printf("请输入数组中的元素的值：\n"); for (i = 0; i < 10; i++) { printf("a[%d]=", i); scanf_s("%d", &a[i]); } for (i = 9; i > 0; i--) { for (j = 0; j <= i; j++) { if (a[j] < a[j+1]) { iTemp = a[j + 1]; a[j + 1] = a[j]; a[j] = iTemp; } } } //输出 for (i = 0; i < 10; i++) { printf("%d ", a[i]); if (i == 4) printf("\n"); } return 0; }

运行结果就不放图了，与第一个相同，都是递减。

三、交换法排序

       交换法排序是将每一位数与其其后的所有书一一比较，如果发现符合条件的数据则进行交换数据。

递增示例如下：

#include<stdio.h> int main() { int i, j; int a[10]; int iTemp; int iPos; printf("请输入数组中的元素的值：\n"); for (i = 0; i < 10; i++) { printf("a[%d]=", i); scanf_s("%d", &a[i]); } for (i = 0; i < 9; i++) { for (j = i + 1; j < 10; j++) { if (a[j] < a[i]) { iTemp = a[i]; a[i] = a[j]; a[j] = iTemp; } } } //输出 for (i = 0; i < 10; i++) { printf("%d ", a[i]); if (i == 4) printf("\n"); } return 0; }

四、插入法排序

       插入法的基本工作原理是抽取一个数据，排在第一位（假设是递减）然后再取后面一个数据与与第一个数据比较，比第一个数据大就放在第一个数据前面，反之放在后面，接下来就是设置类似的嵌套循环，最终完成比较。

#include<stdio.h> int main() { int i, j; int a[10]; int iTemp; int iPos; printf("请输入数组中的元素的值：\n"); for (i = 0; i < 10; i++) { printf("a[%d]=", i); scanf_s("%d", &a[i]); } for (i = 1; i < 10; i++) { iTemp=a[i]; iPos = i - 1; while ((iPos >= 0) && (iTemp < a[iPos])) { a[iPos + 1] = a[iPos]; iPos--; } a[iPos + 1] = iTemp; } //输出 for (i = 0; i < 10; i++) { printf("%d ", a[i]); if (i == 4) printf("\n"); } return 0; }

五、折半法排序

       折半法排序是一种相比起前面的方法更为快速的排序方法，他的基本工作原理是先选取一个中间值，（递增）然后把比中间值小的放在左边，比中间值大的放在右边。

#include<stdio.h> void Choose(int left, int right, int array[]); int main() { int i, a[8]; printf("请输入数组中的元素的值：\n"); for (i = 0; i < 8; i++) { printf("a[%d]=", i); scanf_s("%d", &a[i]); } Choose(0, 7, a); printf("8个元素升序排列如下："); for (i = 0; i < 8; i++) { printf("%d ", a[i]); if (i == 4) printf("\n"); } printf("\n"); return 0; } void Choose(int left, int right, int array[]) { int i, j; int middle, iTemp; i = left; j = right; middle = array[(left + right) / 2]; do { while ((array[i] < middle) && (i < right)) i++; while ((array[j] > middle) && (j > left)) j--; if (i <= j) { iTemp = array[i]; array[i] = array[j]; array[j] = iTemp; i++; j--; } } while (i <= j); if (left < j) Choose(left, j, array); if (right > i) Choose(i, right, array); }

 今天的数组排序就到这里，886：）