13被浏览5,223分享邀请回答2715 条评论分享收藏感谢收起2添加评论分享收藏感谢收起C语言——选择法排序C语言——选择法排序清风sm百家号选择法是被较多采用的一种排序方法，其效率比冒泡法高（交换数据的次数少），而算法却并未复杂多少。选择法排序总的思路是：1、找出一个最小数，交换到最前面。2、在剩下的数里面，再找一个最小的，交换到剩下数的最前面3、重复步骤2 ，直到所有数都已排好。显然，对于含有N个数的数组来说，其过程也要进行N-1趟 ( 0 &= i & N-1 )。上面所述步骤中，“找出一个最小数，交换到最前面”的方法是：先将剩下数中的第一个数（序号是i）作为擂主，用变量k记下其序号，后面的数依次与擂主（注意：擂主是a[k]，不总是a[i]）比较，若比擂主还小，则用k记下其序号（注意：此时不要交换），当所有数都与擂主比较后，k中存放的就是最小数的序号，然后将它交换到最前面（现在才交换）。在上面的过程中，数据只交换了一次，即每趟只交换一次数据。#include&stdio.h&int main(){
int n,i,j,k,temp,a[100];
scanf(&%d&,&n);
for(i=0;i&n;i++)
scanf(&%d&,&a[i]);
for(i=0;i&9;i++)
for(j=i+1;j&n;j++)
if(a[j]&a[k])
temp=a[k];
a[k]=a[i];
for(i=0;i&n;i++)
printf(&%d &,a[i]);
return 0;}本文仅代表作者观点，不代表百度立场。系作者授权百家号发表，未经许可不得转载。清风sm百家号最近更新：简介:最简单的即是最美的。作者最新文章相关文章算法一直是编程的基础，而排序算法是学习算法的开始，排序也是数据处理的重要内容。所谓排序是指将一个无序列整理成按非递减顺序排列的有序序列。排列的方法有很多，根据待排序序列的规模以及对数据的处理的要求，可以采用不同的排序方法。那么就整理下网上搜索的资料，按自己的理解，把C语言的8大排序算法列出来。
普通意义上，排序算法可以分为三大类：
1 交换类排序法2 插入类排序法3&选择类排序法
一.交换类排序法
所谓交换排序法是指借助数据元素之间互相交换进行排序的方法。冒泡排序与快速排序法都属于交换类排序方法。
1、冒泡排序（BubbleSort）
冒泡排序的基本概念：
依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。
外循环变量设为i，内循环变量设为j。假如有10个数需要进行排序，则外循环重复9次，内循环依次重复9，8，...，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,...,9，对于每一个i,j的值依次为1,2,...10-i。
C语言实现：
1 void Bublesort(int a[],int n)
int i,j,k;
for(j=0;j&n;j++)
/* 气泡法要排序n次*/
for(i=0;i&n-j;i++)
/* 值比较大的元素沉下去后，只把剩下的元素中的最大值再沉下去就可以啦 */
if(a[i]&a[i+1])
/* 把值比较大的元素沉到底 */
a[i]=a[i+1];
性能分析：
若记录序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次比较，且不移动记录；反之，若记录序列的初始状态为"逆序"，则需进行n(n-1）/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。
博客园中，有一篇博文是关于冒泡算法的优化，可以看下，两种优化：
2、快速排序（Quicksort）
基本思想：
快速排序是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
设要排序的数组是A[0]&&A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即&key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索（j -- ），找到第一个小于key的值A[j]，A[i]与A[j]交换；
4）从i开始向后搜索，即由前开始向后搜索（i ++ ），找到第一个大于key的A[i]，A[i]与A[j]交换；
5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。）
举例说明：
如无序数组[6 2 4 1 5 9]
a),先把第一项[6]取出来,
用[6]依次与其余项进行比较,
如果比[6]小就放[6]前边,2 4 1 5都比[6]小,所以全部放到[6]前边
如果比[6]大就放[6]后边,9比[6]大,放到[6]后边,//6出列后大喝一声,比我小的站前边,比我大的站后边,行动吧!霸气十足~
一趟排完后变成下边这样:
排序前&6&2 4 1 5&9
排序后&2 4 1 5&6&9
b),对前半拉[2 4 1 5]继续进行快速排序
重复步骤a)后变成下边这样:
排序前&2&4 1 5
排序后 1&2&4 5
前半拉排序完成,总的排序也完成:
排序前:[6 2 4 1 5 9]
排序后:[1 2 4 5 6 9]
C语言实现：
1 　int partition(int *data,int low,int high)
int t = 0;
6 　　t = data[low];
8 　　while(low & high)
10 　　{ while(low & high && data[high] &= t)
12 　　high--;
14 　　data[low] = data[high];
16 　　while(low & high && data[low] &= t)
18 　　low++;
20 　　data[high] = data[low];
24 　　data[low] =
26 　　return
30 　　void sort(int *data,int low,int high) //快排每趟进行时的枢轴要重新确定，由此进 //一步确定每个待排小记录的low及high的值
32 　　{ if(low &= high)
34 　　return ;
36 　　int pivotloc = 0;
38 　　pivotloc = partition(data,low,high);
40 　　sort(data,low,pivotloc-1);
42 　　sort(data,pivotloc+1,high);
快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。
最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。时间复杂度为O(n*n)
在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlgn)
尽管快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。
这里有一个视频比较形象地说明了这两个有趣的排序算法：
阅读(...) 评论()C语言基本排序算法之桶式排序实例
转载 & & 作者：liyuxia713
这篇文章主要介绍了C语言基本排序算法之桶式排序,简单说明了桶式排序的原理并结合具体实例给出了C语言实现桶式排序算法的具体步骤与相关操作技巧,需要的朋友可以参考下
本文实例讲述了C语言基本排序算法之桶式排序。分享给大家供大家参考，具体如下：
桶式排序是对一个有n个整型元素的数组a[n],其中对任意i，0 &= a[i] &= m的特殊排序算法。
可以对 n==m, n != m分别处理。写代码时需要注意的的是a[i]是访问第i-1个元素，而非第i个。
/************************************************************************************/
/* Bucket_Sort.h 桶式排序算法 */
/* 问题：对一个有n个整型元素a[0],a[1],…,a[n-1]的数组排序，其中0 &= a[i] &= m,任意i */
/* 程序：运行时间为O(m+n),辅助空间为O(m) */
/* 当 n=m 时特殊处理，运行时间为O(N), 辅助空间为O(1) */
/************************************************************************************/
#include &vector&
/*m != n */
void Bucket_Sort_m(int *a, int n, int m)
std::vector&int& temp(m,0);
for(i = 0; i != ++i) //遍历a[]
++temp[a[i]-1]; //如果有对应于下标的值，标记为1，否则为0
for(int j = 1; j &= ++j) //遍历temp向量
if(temp[j-1]) a[i++] =
temp.clear();
/* m == n */
/* 最后的结果是a[i-1] = i */
void Bucket_Sort(int *a,int n)
for(int i = 1; i &= ++i)
while(a[i-1] != i)
int temp = a[a[i-1]-1];
a[a[i-1]-1] = a[i-1];
/* 伪代码:如果假设可以通过a[i]访问数组的第i个元素，而不是第i-1个 */
/*while(a[i] != i)
int temp = a[a[i]];
a[a[i]] = a[i];
希望本文所述对大家C语言程序设计有所帮助。
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具几种常见排序算法原理&C语言实现 - gnosed_coding - 博客园
First or best
一、冒泡排序（以下各法均以从小到大排序为例，定义len为数组array的长度）
原理：比较相邻元素的大小，对于每次循环，按排序的规则把最值移向数组的一端，同时循环次数依次减少。
void bubble_sort(int arr[],int len)//从数组头部开始，某一个元素与其后面的每个元素作比较
int i,j，t;
for(i=<span style="color: #;i&len-<span style="color: #;i++)
for(j=i+<span style="color: #;j&j++)
if(arr[i]&arr[j])
t=arr[i];arr[i]=arr[j];arr[j]=t;
void bubble_sort(int arr[],int len)//从数组的头部开始，相邻元素之间作比较
int i,j,t;
for(i=<span style="color: #;i&len-<span style="color: #;i++)
for(j=<span style="color: #;j&len-<span style="color: #-i;j++)
if(arr[j]&arr[j+<span style="color: #])
t=arr[j];arr[j]=arr[j+<span style="color: #];arr[j+<span style="color: #]=t;
void&bubble_sort(int arr[],int len)//从数组的结尾开始返回，相邻元素之间作比较
int i,j,t;
for(i=<span style="color: #;i&i++)
for(j=len-<span style="color: #;j&i;j--)
if(arr[j-<span style="color: #]&arr[j])
t=arr[j];arr[j]=arr[j-<span style="color: #];arr[j-<span style="color: #]=t;
二、选择排序
1.原理：先在未排序的数组中找出最值，通过交换将其放在数组第一位，然后再从剩余的未排序数组中找到另一个最值，将其放在已排序数组的末尾（第二次找到该最值后将其放在数组第二位）。以此类推，直到整个数组排完序。
2.C代码实现
void select_sort(int arr[],int len)
int i,j,t,k;
for(i=<span style="color: #;i&len-<span style="color: #;i++)
for(j=i+<span style="color: #;j&j++)
if(arr[k]&arr[j])//找最小值
t=arr[i];arr[i]=arr[k];arr[k]=t;
三、插入排序（此处为直接插入排序，另外还有二分插入、链表插入等排序）
1.原理：将数据分为有序数列和无序数列两部分，一开始有序数列只有数列的第一个元素。对于无序数列的每个元素，要插入到有序数列中，方法是与有序数列中的末尾元素开始作比较，若前者大于后者则前者位置不变；否则，检索这个待插入元素小于第n个元素且大于或等于第n-1个元素的位置，同时将这个位置后面的元素往后移动(检索一次，移动一次)，然后将其插入到这个位置。以此类推，直到无序数列元素个数为0。
2.C代码实现
void insert_sort(int arr[],int len)
int i,j,k;
for(i=<span style="color: #;i&=i++)
j=i-<span style="color: #;
while(j&-<span style="color: #&&k&arr[j])
arr[j+<span style="color: #]=arr[j];
arr[j+<span style="color: #]=k;
四、快速排序
首先选取未排序数组的第一个数作为关键数据，然后，将所有比它小的数都放到它前面，将所有比它大的数都放到它后面，这个过程称为一趟快速排序。然后再对前后这两个数组进行类似排序，直到整个数组排好序。不难看出，这里最好采用到递归。具体算法步骤参见http://developer.51cto.com/art/986.htm
2.C代码实现
void quick_sort(int ary[],int left,int right)
int i=left,j=right,k=ary[left],t;//k储存准基数
while(i!=j)
while(i&j&&ary[j]&=k)//必须是先从右边比较，否则准基数归位时将出错
while(i&j&&ary[i]&=k)
t=ary[i];ary[i]=ary[j];ary[j]=t;
ary[left]=ary[i];
quick_sort(ary,left,i-<span style="color: #);
quick_sort(ary,i+<span style="color: #,right);
五、归并排序
1.原理：归并排序采用递归实现，总体上有两个步骤（分解与归并）：
先将待排序数组R[0...n-1]分解成n个长度为1的有序序列（其实是一个元素），将相邻的两个元素有序归并，得到n/2个长度为2的有序序列；然后将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。
归并的具体步骤：比较arr[i]和arr[j],将较小值复制到新的数组new_arr[k],同时让i，j都加上1。如此循环下去，直到其中一个数组被复制完，再让另一个数组所剩余的元素（已排序）直接拼接到的new_arr的后面。
2.C代码实现
void merge_sort2(int arr[],int new_arr[],int left,int right,int mid)
int i=left,j=mid+<span style="color: #,k=
while(i!=mid+<span style="color: #&&j!=right+<span style="color: #)//归并
if(arr[i]&arr[j])
new_arr[k++]=arr[j++];
new_arr[k++]=arr[i++];
while(i!=mid+<span style="color: #)
new_arr[k++]=arr[i++];
while(j!=right+<span style="color: #)
new_arr[k++]=arr[j++];
for(i=i&=i++)
arr[i]=new_arr[i];
void merge_sort1(int arr[],int new_arr[],int left,int right)
if(left&right)
mid=(left+right)/<span style="color: #;
merge_sort1(arr,new_arr,left,mid);//左分解
merge_sort1(arr,new_arr,mid+<span style="color: #,right);//右分解
merge_sort2(arr,new_arr,left,right,mid);//调用子函数归并