常用排序算法的C语言版实现示例整理
所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下：
输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。
输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。
排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。基本的排序算法有如下几种：交换排序（冒泡排序、快速排序）、选择排序（直接选择排序、堆排序）、插入排序（直接插入排序、希尔排序）、归并排序、分配排序（基数排序、箱排序、计数排序）。下面依次列出各种算法的代码，并进行简要分析。分配排序算法的代码没有列出。
（1）快速排序：快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。最好、平均复杂度都为O(nlogn)，最坏为O(n^2)。
void quick_sort1(int a[],int l,int r)
{
if(l >= r)
return;
int i, j, p;
i = l-1, j = l,p = a[r];
while(j < r)
{
if(a[j] < p)
swap(a[++i], a[j]);
j++;
}
swap(a[++i], a[r]);
quick_sort1(a, l, i-1);
quick_sort1(a, i+1, r);
}
《算法导论》一书中，给出了这个程序的伪代码。当数组元素相等、逆序、顺序排列时，调用这个程序会导致栈溢出。因为每次划分都是最坏坏分。可以改进一下。上述程序每次选的划分基准元素都是固定的，如果是随机产生的，那么可以大大降低出现最坏划分的概率。
void quick_sort2(int a[],int l,int r)
{
if(l >= r)
return;
int i,j,p;
i = l-1,j = l;
p=l + rand()%(r-l); //随机产生[l,r)之间的数
swap(a[p], a[r]);
p = a[r];
while(j < r)
{
if(a[j] < p)
swap(a[++i], a[j]);
j++;
}
swap(a[++i], a[r]);
quick_sort2(a, l, i-1);
quick_sort2(a, i+1, r);
}
但是，当数组元素相等时，还是出现了栈溢出。可以做如下调整。
void quick_sort3(int a[],int l,int r)
{
if(l >= r)
return;
int i,j,p;
i = l-1, j = r, p = a[r];
while(1)
{
do { i++; } while(a[i] < p && i < r);
do { j--; } while(a[j] > p && j > l);
if(i >= j)
break;
swap(a[i], a[j]);
}
swap(a[i],a[r]);
quick_sort3(a, l, i-1);
quick_sort3(a, i+1, r);
}
但是，当数组元素顺序，逆序时，同样出现了栈溢出。若将两者结合起来，就可以尽量避免栈溢出。
void quick_sort4(int a[],int l,int r)
{
if(l >= r)
return;
int i,j,p;
i = l-1, j = r;
p = l + rand()%(r-l);
swap(a[p],a[r]);
p = a[r];
while(1)
{
do { i++; } while(a[i] < p && i < r);
do { j--; } while(a[j] > p && j > l);
if(i >= j)
break;
swap(a[i], a[j]);
}
swap(a[i], a[r]);
quick_sort4(a, l, i-1);
quick_sort4(a, i+1, r);
}
（2）冒泡排序：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。
void bubble_sort1(int a[],int n)
{
int i,j;
for(i = 0; i < n-1; i++)
{
for(j = i+1; j < n; j++)
{
if(a[i] > a[j])
swap(a[i], a[j]);
}
}
}
可以稍作改进，当数组数元素顺序时，时间复杂度为O(n)。加入一个变量，如果在一遍扫描中，没有出现交换，那么结束排序，因为数组已排好序了。
void bubble_sort2(int a[],int n)
{
int i,j;
for(i = 0; i < n-1; i++)
{
bool exchange = false;
for(j = i+1; j < n; j++)
{
if(a[i] > a[j])
{
exchange = true;
swap(a[i], a[j]);
}
}
if(exchange == false)
break;
}
}
经网友指出，上面这个冒泡排序有问题，无法得到正确结果。下面引自网友的正确写法：
void bubble_sort2(int a[],int n)
{
int i,j;
for(i = 0;i < n-1; i++)
{
bool exchange = false;
for(j = n-1;j > i; j--)
{
if(a[j-1] > a[j])
{
exchange = true;
swap(a[j-1], a[j]);
}
}
if(exchange == false)
break;
}
}
（3）直接选择排序：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。
void select_sort1(int a[],int n)
{
int i,j;
for(i = 0; i < n-1; i++)
{
int min = i;
for(j = i+1; j < n; j++)
{
if(a[j] < a[min])
min = j;
}
if(min != i)
swap(a[i], a[min]);
}
}
（4）堆排序：根据输入数据，利用堆的调整算法形成初始堆，然后交换根元素与尾元素，总的元素个数减1，然后从根往下调整。堆排序的最好、最坏、平均时间复杂度都为O(nlogn)
void heap_siftdown(int a[],int n,int p) //调整算法
{
int i = p,j = i*2+1;
int tmp = a[i];
while(j < n)
{
if(j+1 < n && a[j] < a[j+1])
j++;
if(a[j] <= tmp)
break;
else
{
a[i] = a[j];
i = j;j = j*2+1;
}
}
a[i] = tmp;
}
void heap_sort1(int a[],int n)
{
int i;
for(i = (n-1)/2; i >= 0;i--)
heap_siftdown(a, n, i);
for(i = n-1;i >= 0; i--)
{
swap(a[i], a[0]);
heap_siftdown(a, i, 0);
}
}
（5）直接插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。当数组已经排好序，直接插入排序的时间复杂度为O(n)
void insert_sort1(int a[],int n)
{
int i,j;
for(i = 1; i < n; i++)
{
for(j = i; j > 0 && a[j]<a[j-1]; j--)
swap(a[j-1], a[j]);
}
}
如果将交换函数展开，可以加快排序的速度。
void insert_sort2(int a[],int n)
{
int i,j;
for(i = 1; i < n; i++)
{
for(j = i; j > 0 && a[j] < a[j-1]; j--)
{
int t = a[j-1];
a[j-1] = a[j];
a[j] = t;
}
}
}
可以进一步改进，insert_sort2的算法不断给t赋值，可以将赋值语句移到循环外面。
void insert_sort3(int a[],int n)
{
int i,j;
for(i = 1;i < n; i++)
{
int t = a[i];
for(j = i; j > 0 && a[j-1] > t; j--)
a[j] = a[j-1];
a[j] = t;
}
}
（6）希尔排序：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
最后一遍的增量必须是1，其实是就是调用直接插入排序算法。
void shell_sort1(int a[],int n)
{
int i = n;
do{
i = i/3 + 1;
shell_pass1(a, n, i);
}while(i > 1);
}
void shell_pass1(int a[],int n,int inc) //inc为1时，其实就是直接插入排序
{
int i,j;
for(i = inc; i < n; i++)
{
int t=a[i];
for(j = i;j >= inc && a[j-inc] > t; j-= inc)
a[j] = a[j-inc];
a[j] = t;
}
}
（7）归并排序：利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。可以用于外排序。
void merge_sort1(int a[],int b[],int l,int r)
{
if(l >= r)
return;
int m = (l+r)/2;
merge_sort1(a, b, l, m);
merge_sort1(a, b, m+1, r);
merge1(a, b, l, m, r);
}
void merge1(int a[],int b[],int l,int m,int r)
{
int i,j,k;
for(i = l; i <= r; i++)
b[i] = a[i];
i = l; j = m+1; k = l;
while(i <= m && j <= r)
{
if(b[i] <= b[j]) a[k++] = b[i++];
else a[k++] = b[j++];
}
while(i <= m) a[k++] = b[i++];
while(j <= r) a[k++] = b[j++];
}
给出上述算法的程序的测试驱动程序及两个辅助程序。要测试某种排序算法，只需将注释去掉即可。
#include <iostream>
#include <ctime>
using namespace std;
const int N = 100;
int a[N];
int b[N];
int main()
{
int i;
srand(time(0));
//for(i=0;i<N;i++)
// a[i]= N-i;
for(i = 0;i < N; i++)
a[i]=rand()%N;
long start,end;
start = clock();
//quick_sort1(a,0,N-1);
//quick_sort2(a,0,N-1);
//quick_sort3(a,0,N-1);
//quick_sort4(a,0,N-1);
//bubble_sort1(a,N);
//bubble_sort2(a,N);
//merge_sort1(a,b,0,N-1);
//heap_sort1(a,N);
//shell_sort1(a,N);
//select_sort1(a,N);
//insert_sort1(a,N);
//insert_sort2(a,N);
//insert_sort3(a,N);
end = clock();
print_array(a, N);
cout<<"total time is : "<<(end-start)/1000.0<<'s'<<endl;
return 0;
}
void swap(int a[],int i,int j) //交换元素
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
void print_array(int a[],int n) //打印元素值
{
for(int i = 0; i < n; i++)
{
cout<<a[i]<<' ';
if(i%10==0 && i!=0)
cout<<endl;
}
cout<<endl;
}
您可能感兴趣的文章
- 04-02c语言编写函数冒泡排序 c语言冒泡排序法函数
- 01-10使用C++实现全排列算法的方法详解
- 01-10深入第K大数问题以及算法概要的详解
- 01-10深入N皇后问题的两个最高效算法的详解
- 01-10用C++实现DBSCAN聚类算法
- 01-10深入全排列算法及其实现方法
- 01-10全排列算法的非递归实现与递归实现的方法(C++)
- 01-10深入理解堆排序及其分析
- 01-10深入单链表的快速排序详解
- 01-10贪心算法 WOODEN STICKS 实例代码
阅读排行
本栏相关
- 04-02c语言函数调用后清空内存 c语言调用
- 04-02func函数+在C语言 func函数在c语言中
- 04-02c语言的正则匹配函数 c语言正则表达
- 04-02c语言用函数写分段 用c语言表示分段
- 04-02c语言中对数函数的表达式 c语言中对
- 04-02c语言编写函数冒泡排序 c语言冒泡排
- 04-02c语言没有round函数 round c语言
- 04-02c语言分段函数怎么求 用c语言求分段
- 04-02C语言中怎么打出三角函数 c语言中怎
- 04-02c语言调用函数求fibo C语言调用函数求
随机阅读
- 08-05DEDE织梦data目录下的sessions文件夹有什
- 08-05dedecms(织梦)副栏目数量限制代码修改
- 08-05织梦dedecms什么时候用栏目交叉功能？
- 01-10使用C语言求解扑克牌的顺子及n个骰子
- 01-11ajax实现页面的局部加载
- 01-10delphi制作wav文件的方法
- 01-11Mac OSX 打开原生自带读写NTFS功能(图文
- 01-10SublimeText编译C开发环境设置
- 04-02jquery与jsp,用jquery
- 01-10C#中split用法实例总结