C语言实现选择排序、冒泡排序和快速排序的代码示例

选择和冒泡

#include<stdio.h> 

 void maopao(int a[],int len){
   int i,j,temp;
   for(i = 0;i < len - 1 ; i ++){//从第一个到倒数第二个
     for (j = 0 ; j < len - 1 - i ; j ++)//排在后的是已经排序的
     {
       if (a[j] > a[j + 1])//大的数换到后面去
       {
         temp = a[j];
         a[j] = a[j + 1];
         a [j + 1] = temp;
       }
     }
   }
 } 

 void xuanze(int a[],int len){
   int i , j , t , temp;
   for (i = 0 ; i < len - 1 ;i ++)
   {
     t = i;
     for (j = i + 1 ; j < len ; j ++)//前面的实排好的
     {
       if (a[t] > a[j])
       {
         t = j;//记下该趟最小数的序号
       }
     }
     if (t != i)//如果序号不变就什么也不做
     {
       temp = a[t];//否则元素交换
       a[t] = a[i];
       a[i] = temp;
     }
   }
 } 

 void main(){
   int i;
   int a[] = {5,4,6,7,2,5,4,6,8,9,1,2};
   //maopao(a, 12);
   xuanze(a, 12);
   for (i = 0 ; i < 12 ; i ++)
   {
     printf("%d ",a[i]);
   }
 }

快速排序与冒泡、选择的比较:

#include <stdio.h>
#include <time.h>
#include <windows.h> 

//快速排序,参数是数组,最低索引,最高索引(从0开始)
void qSort(int a[], int low, int high){
  int temp;
  int mid = low;//定义一个中索引,用于记录一次排序后确定位置的一个元素索引
  int right = high;//记录最右元素索引 

  //默认中值是左值,现在要把凡是比中值大的元素放到中值左边
  while(right > mid){//因此从右开始向中值遍历,到达中值时遍历结束
    if (a[right] < a[mid])//如果右值比中值还小,说明他不该在右边,要把它放到左边
    {
      temp = a[mid];//所以先把中值的地盘腾出来
      a[mid] = a[right];//把比中值小的那个数放在那儿
      //中值没地方放,必须右移移位,但是直接右移会覆盖原来他右边的那个值
      a[right] = a[++mid];//不过right索引的空间已经腾出来了,就把中值原来右边的值放到right
      a[mid] = temp;//然后就可以把mid右移一位
    }
    else{
      right--;//否则的话说明right已然大于等于mid,不用移动,继续判断right左边那个数
    }
  }//这样right与mid重合之时,退出循环,此时mid的位置已经确定了就是排完序后他的位置
   //因为他左边的都比他小,右边的都比他大
  if (mid - low > 1)//如果low到mid之间还有两个或以上元素,还要对他们排序
  {
    qSort(a, low, mid - 1);
  } 

  if (high - mid > 1)//右边那半也是一样
  {
    qSort(a, mid + 1, high);
  }
} 

void sSort(int a[], int len){//选择排序,参数是数组名和元素个数
  int i, j, m, temp;
  for (i = 0; i < len - 1; i++)//从开始到倒数第二个元素
  {
    m = i;//先记录最左边的元素索引,假设他为最小
    for (j = i + 1; j < len; j++)//从左往右遍历一直到最后
    {
      if (a[j] < a[m])//如果发现更小的元素
      {
        m = j;//记下这个元素的索引
      }
    }
    if (m != i)//如果最小的元素不是开始那个,就需要把最小的换到最左边
    {
      temp = a[i];
      a[i] = a[m];
      a[m] = temp;
    }
  }
} 

void mSort(int a[], int len){//冒泡法排序,参数是数组名,元素个数
  int i, j, temp;
  for (i = 0; i < len - 1; i ++)//从开始到倒数第二个元素
  {
    for (j = 0; j < len - 1 - i; j++)//从头遍历到已序队列往前第二个
    {
      if (a[j] > a[j + 1])//如果元素比他的后一个大,则交换
      {
        temp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = temp;
      }
    }//一次遍历后最大元素放到最后面
  }
} 

int checkSorted(int a[], int len){//检查数组排序是否已经正确
  int i;
  for (i = 0; i < len - 1; i++)
  {
    if (a[i] > a[i + 1])//如果一个元素比他的下一个还要大,说明发生错误
    {
      return 0;
    }
  }
  return 1;
} 

void main(){
  int i, j;
  int a[99999]; 

  clock_t begin, end;
  double cost; 

  for (j = 0; j < 6; j++)//做6次测试
  {
    srand((int)time(0));//用时间做种,是每次数字都不同
    for (i = 0; i < 99999; i++)
    {
      a[i] = rand();//产生随机数放入数组
    } 

    begin = clock(); 

    //qSort(a, 0, 99998);//1秒左右
    //sSort(a, 99999);//20秒左右
    mSort(a, 99999);//40秒左右 

    end = clock(); 

    for (i = 0; i < 12; i++)//输出前面的几个排好序的元素
    {
      printf("%d ", a[i]);
    } 

    cost = (double)(end - begin) / CLOCKS_PER_SEC;//计算排序时间
    printf("...\t排序用时 %lf 秒 ", cost);//输出排序所用时间 

    if (checkSorted(a, 99999))//检查排序是否正确
    {
      printf("正确!\n");
    }else{
      printf("有错!\n");
    }
    Sleep(1200);//暂停一下,使每次时间种子不同
  }
}

1. 快速排序的结果:
 99999个随机数一般不超过0.05秒,很快
2.选择法排序结果:

99999个随机数一般不超过0.05秒,很快
2.选择法排序结果:

一般在20多秒;
3.冒泡法,一般情况下交换的次数会很多,结果:

排序时间一般在50秒左右,最慢。
 
在C++中,还可以定义函数模板
因为快速排序通常很快,所以用它来对不同的数据类型排序

#include <iostream.h> 

template<class T> void qSort(T a[], int low, int high){//在C++中,可以定义函数模板
  T temp;
  int mid = low;
  int right = high; 

  while (right > mid)
  {
    if (a[right] < a[mid])
    {
      temp = a[mid];
      a[mid] = a[right];
      a[right] = a[++mid];
      a[mid] = temp;
    }else{
      right--;
    }
  }
  if (mid - low > 1)
  {
    qSort(a, low, mid - 1);
  }
  if (high - mid > 1)
  {
    qSort(a, mid + 1, high);
  }
} 

void main(){
  int a[10] = {1, 9, 6, 3, 5, 7, 1};//有了一个函数模板,可以对整型排序
  qSort(a, 0, 9);
  for (int i = 0; i < 10; i++)
  {
    cout<<a[i]<<" ";
  }
  cout<<endl; 

  float b[10] = {2.0f, 1.2f, 5.5f, 6.63f, 9.11f, 1.32f, 3.44f, 5.0f, 5.22f, 0.02f};
  qSort(b, 0, 9);//对浮点数排序
  for (i = 0; i < 10; i++)
  {
    cout<<b[i]<<" ";
  }
  cout<<endl; 

  char c[10] = {'d','e','f','n','j','c','e','b','f','a'};//对字符数组排序
  qSort(c, 0, 9);
  for (i = 0; i < 10; i++)
  {
    cout<<c[i]<<" ";
  }
  cout<<endl;
}//凡是可以用‘<'来比较大小的类型都可以排序了

(0)

相关推荐

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

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

  • C语言实现选择排序、直接插入排序、冒泡排序的示例

    选择排序 选择排序是一种简单直观的排序算法,其核心思想是:遍历数组,从未排序的序列中找到最小元素,将其放到已排序序列的末尾. 时间复杂度:O(n^2) 稳定性 :不稳定 /* * @brief selection sort */ void selection_sort(int a[], int n) { int i, j, min, tmp; for (i = 0; i < n - 1; ++i) { min = i; for (j = i+1; j < n; ++j) { if (a[j]

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

    所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来.其确切定义如下: 输入:n个记录R1,R2,-,Rn,其相应的关键字分别为K1,K2,-,Kn. 输出:Ril,Ri2,-,Rin,使得Ki1≤Ki2≤-≤Kin.(或Ki1≥Ki2≥-≥Kin).     排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量.基本的排序算法有如下几种:交换排序(冒泡排序.快速排序).选择排序(直接选择排序.堆排序).插入排序(直接插入排序.希尔排序).归并排序.分配排序(基数排

  • 希尔排序算法的C语言实现示例

    希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本.希尔排序是非稳定排序算法. 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能.这样可以让一个元素可以一次性地朝最终位置前进一大步.然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几

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

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

  • C语言实现冒泡排序算法

    BubblSort.c #include<stdio.h> void BubbleSort(int a[],int len) { int i; int j; int h; int temp; for(i=0;i<len-1;++i) { for(j=len-1;j>i;--j) { if(a[j]<a[j-1]) { temp=a[j]; a[j]=a[j-1]; a[j-1]=temp; } } for(h=0;h<len;h++) { printf(" %

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

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

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

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

  • c语言实现奇偶排序算法

    =====第2题:奇偶排序(一)===== 总时间限制:1000ms内存限制:65536kB描述输入十个整数,将十个整数按升序排列输出,并且奇数在前,偶数在后.输入输入十个整数输出按照奇偶排序好的十个整数 复制代码 代码如下: #include<stdio.h> #define  COUNT 10#define bool int#define true 1#define false 0 /*****负责冒泡排序***/int* sortFunction(int data[]){ int i,j

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

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

  • C语言的冒泡排序和快速排序算法使用实例

    冒泡排序法 题目描述: 用一维数组存储学号和成绩,然后,按成绩排序输出. 输入: 输入第一行包括一个整数N(1<=N<=100),代表学生的个数.     接下来的N行每行包括两个整数p和q,分别代表每个学生的学号和成绩. 输出: 按照学生的成绩从小到大进行排序,并将排序后的学生信息打印出来.     如果学生的成绩相同,则按照学号的大小进行从小到大排序. 样例输入: 3     1 90     2 87     3 92 样例输出: 2 87     1 90     3 92 代码: #

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

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

随机推荐