C语言七种排序方法.pdfVIP

（） 冒泡法 1 “ ” 冒泡法大家都较熟悉。其原理为从 开始，依次将其和后面的元素比较若 ，则 a[0] , a[0]a[i] 交换它们，一直比较到a[n]。同理对a[1],a[2],...a[n-1]处理，即完成排序。下面列出其代 码： void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/ { int i,j,temp; for(i 0;in-1;i++) for(j i+1;jn;j++)/*注意循环的上下限*/ if(a[i]a[j]) { temp a[i]; a[i] a[j]; a[j] temp; } } 冒泡法原理简单，但其缺点是交换次数多，效率低。 下面介绍一种源自冒泡法但更有效率的方法 选择法 。 “ ” （） 选择法 2 “ ” 选择法循环过程与冒泡法一致，它还定义了记号 然后依次把 同后面元素比较，若 k i, a[k] a[k]a[j],则使k j.最后看看k i 是否还成立，不成立则交换a[k],a[i],这样就比冒泡法省下 许多无用的交换，提高了效率。 void choise(int *a,int n) { int i,j,k,temp; for(i 0;in-1;i++) { k i;/*给记号赋值*/ for(j i+1;jn;j++) 是 总是指向最小元素 if(a[k]a[j]) k j;/* k */ 当 是才交换，否则 即为最小 if(i! k) {/* k! i a[i] */ temp a[i]; a[i] a[k]; a[k] temp; } } } 选择法比冒泡法效率更高，但说到高效率，非 快速法 莫属，现在就让我们来了解它。 “ ” （） 快速法 3 “ ” 快速法定义了三个参数，（数组首地址 要排序数组起始元素下标 要排序数组结束元素下 *a, i, 标j). 它首先选一个数组元素 （一般为a[(i+j)/2],即中间元素）作为参照，把比它小的元素 放到它的左边，比它大的放在右边。然后运用递归，在将它左，右两个子数组排序，最后 完成整个数组的排序。下面分析其代码： void quick(int *a,int i,intj) { int m,n,temp; int k; m i; n j; k a[(i+j)/2];/*选取的参照*/ do { while(a[m]kmj) m++;/* 从左到右找比k大的元素*/ while(a[n]kni) n--;/* 从右到左找比k小的元素*/ if(m n) {/*若找到且满足条件，则交换*/ temp a[m]; a[m] a[n]; a[n] temp; m++; n--; } }while(m n); if(mj) quick(a,m,j);/*运用递归*/ if(ni) quick(a,i,n); } （） 插入法 4 “ ” 插入法是一种比较直观的排序方法。它首先把数组头两个元素排好序，再依次把后面的元 素插入适当的位置。把数组元素插完也就完成了排序。 void insert(int *a,int n) { int i,j,temp; for(i 1;in;i++) { temp a[i];/*temp为要插入的元素*/ j i-1; while(j 0tempa[j]) {/*从a[i-1]开始找比a[i]小的数，同时把数组元素向后移*/ a[j+1] a[