常用排序算法的C语言版实现示例整理

  • 更新时间:2022-10-17 09:09:09
  • 编辑:怀承允

所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来。其确切定义如下:
  输入: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; 
} 

 

相关教程

  • C语言中字符和字符串处理(ANSI字符和Unicode字符)

    给大家整理了关于C语言的教程,这篇文章主要介绍了C语言与C++中字符和字符串处理(ANSI字符和Unicode字符)的详细内容,非常的全面,这里推荐给大家,希望大家能够喜欢。

    发布时间:2022-09-14

  • 使用C语言详解霍夫曼树数据结构

    使用C语言详解霍夫曼树数据结构

    给大家整理了关于C语言的教程,这篇文章主要介绍了使用C语言详解霍夫曼树数据结构,包括一道AMC相关的例题演示需要的朋友可以参考下

    发布时间:2022-08-01

  • 深度剖析C语言结构体

    给大家整理一篇关于C语言的教程,今天小编就为大家分享一篇关于深度剖析C语言结构体,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧

    发布时间:2022-07-25

  • 探讨C语言的那些小秘密之断言

    探讨C语言的那些小秘密之断言

    给大家整理了关于C语言的教程,我尽可能的把我所理解的断言的使用讲解清楚,希望我在此所讲的断言能够对你有所帮助,让你以后能够在代码中灵活使用断言

    发布时间:2022-07-12

  • c语言构建一个静态二叉树实现方法

    下面小编就为大家带来一篇c语言_构建一个静态二叉树实现方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧

    发布时间:2022-04-04

  • 深入理解C语言指针

    为网友们分享了关于C语言的教程,关于指针,其是C语言的重点,C语言学的好坏,其实就是指针学的好坏。其实指针并不复杂,学习指针,要正确的理解指针

    发布时间:2022-06-22

  • C语言文件操作总结

    本篇文章给大家通过代码示例讲述了C语言文件操作的相关知识点,对此有兴趣的朋友可以参考学习下。

    发布时间:2022-04-06

  • Linux中使用C语言的fork()函数创建子进程的实例教程

    Linux中使用C语言的fork()函数创建子进程的实例教程

    给大家整理了关于C语言的教程,fork是一个在Linux系统环境下专有的函数,现有的进程调用fork后将会创建一个新的进程,这里我们就来看一下Linux中使用C语言的fork()函数创建子进程的实例教程

    发布时间:2022-07-25

用户留言