常用排序算法的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;
}
(0)

相关推荐

  • C语言实现基于最大堆和最小堆的堆排序算法示例

    堆定义 堆实际上是一棵完全二叉树,其任何一非叶节点满足性质: Key[i]<=key[2i+1]&&Key[i]<=key[2i+2](小顶堆)或者:Key[i]>=Key[2i+1]&&key>=key[2i+2](大顶堆) 即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字. 堆排序的思想 利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单. 最大堆:所有节点的子节点比其

  • C语言基本排序算法之插入排序与直接选择排序实现方法

    本文实例讲述了C语言基本排序算法之插入排序与直接选择排序实现方法.分享给大家供大家参考,具体如下: 声明待排序元素类型 /*-------------------------- typedef.h 方便修改待排序元素类型 -------------------------------------*/ #ifndef TYPEDEF_H #define TYPEDEF_H typedef int T; #endif 插入排序: /*---------------------------------

  • C语言排序算法之冒泡排序实现方法【改进版】

    本文实例讲述了C语言排序算法之冒泡排序实现方法.分享给大家供大家参考,具体如下: 冒泡排序和改进的冒泡排序 /*------------------------------------------------------------------------------------------- Bubble_sort.h 冒泡排序: 时间复杂度为O(N^2) 改进的冒泡排序: 时间复杂度仍为O(N^2) 一般的冒泡排序方法有可能会在已经排好序的情况下继续比较,改进的冒泡排序 设置了一个哨兵fla

  • c语言快速排序算法示例代码分享

    步骤为:1.从数列中挑出一个元素,称为 "基准"(pivot);2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边).在这个分区退出之后,该基准就处于数列的中间位置.这个称为分区(partition)操作.3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序.递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了.虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iterat

  • C语言 实现归并排序算法

    C语言 实现归并排序算法 归并排序(Merge sort)是创建在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 一个归并排序的例子:对一个随机点的链表进行排序 算法描述 归并操作的过程如下: 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤3直到某一指针到达序列尾

  • 桶排序算法的理解及C语言版代码示例

    理解: 桶排序是计数排序的变种,把计数排序中相邻的m个"小桶"放到一个"大桶"中,在分完桶后,对每个桶进行排序(一般用快排),然后合并成最后的结果. 基本思想: 桶排序假设序列由一个随机过程产生,该过程将元素均匀而独立地分布在区间[0,1)上.我们把区间[0,1)划分成n个相同大小的子区间,称为桶.将n个记录分布到各个桶中去.如果有多于一个记录分到同一个桶中,需要进行桶内排序.最后依次把各个桶中的记录列出来记得到有序序列. 效率分析: 桶排序的平均时间复杂度为线性的

  • C语言 冒泡排序算法详解及实例

    C语言 冒泡排序算法 冒泡排序(Bubble Sort)是一种简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 冒泡排序对n个项目需要O(n2)的比较次数,且可以原地排序.尽管这个算法是最简单了解和实作的排序算法之一,但它对于少数元素之外的数列排序是很没有效率的. 冒泡排序是与插入排序拥有相等的执

  • C语言基本排序算法之shell排序实例

    本文实例讲述了C语言基本排序算法之shell排序.分享给大家供大家参考,具体如下: shell排序是对直接插入方法的改进方法. /*------------------------------------------------------------------------------------- Shell_sort.h shell排序是对直接插入方法的改进,它并不是对相邻元素进行比较,而是对一定间隔的元素比较. 选择增量序列的几种方法:(为方便,本例采用第一种增量序列) 1. h[1]=

  • C语言基本排序算法之桶式排序实例

    本文实例讲述了C语言基本排序算法之桶式排序.分享给大家供大家参考,具体如下: 桶式排序是对一个有n个整型元素的数组a[n],其中对任意i,0 <= a[i] <= m的特殊排序算法. 可以对 n==m, n != m分别处理.写代码时需要注意的的是a[i]是访问第i-1个元素,而非第i个. /************************************************************************************/ /* Bucket_Sort.h

  • C语言实现排序算法之归并排序详解

    排序算法中的归并排序(Merge Sort)是利用"归并"技术来进行排序.归并是指将若干个已排序的子文件合并成一个有序的文件. 一.实现原理: 1.算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中. (1)合并过程 合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置.合并时依次比较R[i

随机推荐