快捷導(dǎo)航

C語言實(shí)現(xiàn)選擇排序、冒泡排序和快速排序的代碼示例

更新時間：2016年04月09日 14:56:10 作者：hzy3774

這篇文章主要介紹了C++中實(shí)現(xiàn)選擇排序、冒泡排序和快速排序的代碼示例,例子帶有執(zhí)行時間統(tǒng)計(jì)還可以簡單看一下效率對比,需要的朋友可以參考下

選擇和冒泡

#include<stdio.h> 
  
 void maopao(int a[],int len){ 
   int i,j,temp; 
   for(i = 0;i < len - 1 ; i ++){//從第一個到倒數(shù)第二個 
     for (j = 0 ; j < len - 1 - i ; j ++)//排在后的是已經(jīng)排序的 
     { 
       if (a[j] > a[j + 1])//大的數(shù)換到后面去 
       { 
         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 ++)//前面的實(shí)排好的 
     { 
       if (a[t] > a[j]) 
       { 
         t = j;//記下該趟最小數(shù)的序號 
       } 
     } 
     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> 
 
//快速排序，參數(shù)是數(shù)組，最低索引，最高索引(從0開始) 
void qSort(int a[], int low, int high){ 
  int temp; 
  int mid = low;//定義一個中索引，用于記錄一次排序后確定位置的一個元素索引 
  int right = high;//記錄最右元素索引 
   
  //默認(rèn)中值是左值，現(xiàn)在要把凡是比中值大的元素放到中值左邊 
  while(right > mid){//因此從右開始向中值遍歷，到達(dá)中值時遍歷結(jié)束 
    if (a[right] < a[mid])//如果右值比中值還小，說明他不該在右邊，要把它放到左邊 
    { 
      temp = a[mid];//所以先把中值的地盤騰出來 
      a[mid] = a[right];//把比中值小的那個數(shù)放在那兒 
      //中值沒地方放，必須右移移位，但是直接右移會覆蓋原來他右邊的那個值 
      a[right] = a[++mid];//不過right索引的空間已經(jīng)騰出來了，就把中值原來右邊的值放到right 
      a[mid] = temp;//然后就可以把mid右移一位 
    } 
    else{ 
      right--;//否則的話說明right已然大于等于mid，不用移動，繼續(xù)判斷right左邊那個數(shù) 
    } 
  }//這樣right與mid重合之時，退出循環(huán)，此時mid的位置已經(jīng)確定了就是排完序后他的位置 
   //因?yàn)樗筮叺亩急人?，右邊的都比他?
  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){//選擇排序，參數(shù)是數(shù)組名和元素個數(shù) 
  int i, j, m, temp; 
  for (i = 0; i < len - 1; i++)//從開始到倒數(shù)第二個元素 
  { 
    m = i;//先記錄最左邊的元素索引，假設(shè)他為最小 
    for (j = i + 1; j < len; j++)//從左往右遍歷一直到最后 
    { 
      if (a[j] < a[m])//如果發(fā)現(xiàn)更小的元素 
      { 
        m = j;//記下這個元素的索引 
      } 
    } 
    if (m != i)//如果最小的元素不是開始那個，就需要把最小的換到最左邊 
    { 
      temp = a[i]; 
      a[i] = a[m]; 
      a[m] = temp; 
    } 
  } 
} 
 
void mSort(int a[], int len){//冒泡法排序，參數(shù)是數(shù)組名，元素個數(shù) 
  int i, j, temp; 
  for (i = 0; i < len - 1; i ++)//從開始到倒數(shù)第二個元素 
  { 
    for (j = 0; j < len - 1 - i; j++)//從頭遍歷到已序隊(duì)列往前第二個 
    { 
      if (a[j] > a[j + 1])//如果元素比他的后一個大，則交換 
      { 
        temp = a[j]; 
        a[j] = a[j + 1]; 
        a[j + 1] = temp; 
      } 
    }//一次遍歷后最大元素放到最后面 
  } 
} 
 
int checkSorted(int a[], int len){//檢查數(shù)組排序是否已經(jīng)正確 
  int i; 
  for (i = 0; i < len - 1; i++) 
  { 
    if (a[i] > a[i + 1])//如果一個元素比他的下一個還要大，說明發(fā)生錯誤 
    { 
      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));//用時間做種，是每次數(shù)字都不同 
    for (i = 0; i < 99999; i++) 
    { 
      a[i] = rand();//產(chǎn)生隨機(jī)數(shù)放入數(shù)組 
    } 
     
    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;//計(jì)算排序時間 
    printf("...\t排序用時 %lf 秒 ", cost);//輸出排序所用時間 
 
    if (checkSorted(a, 99999))//檢查排序是否正確 
    { 
      printf("正確!\n"); 
    }else{ 
      printf("有錯!\n"); 
    } 
    Sleep(1200);//暫停一下，使每次時間種子不同 
  } 
}

1. 快速排序的結(jié)果：
99999個隨機(jī)數(shù)一般不超過0.05秒，很快
2.選擇法排序結(jié)果：

201649145435207.jpg (481×141)

99999個隨機(jī)數(shù)一般不超過0.05秒，很快
2.選擇法排序結(jié)果：

201649145507759.jpg (499×139)

一般在20多秒；
3.冒泡法，一般情況下交換的次數(shù)會很多，結(jié)果：

201649145531811.jpg (488×152)

排序時間一般在50秒左右，最慢。

在C++中，還可以定義函數(shù)模板
因?yàn)榭焖倥判蛲ǔ：芸?，所以用它來對不同的?shù)據(jù)類型排序

#include <iostream.h> 
 
template<class T> void qSort(T a[], int low, int high){//在C++中，可以定義函數(shù)模板 
  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};//有了一個函數(shù)模板，可以對整型排序 
  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);//對浮點(diǎn)數(shù)排序 
  for (i = 0; i < 10; i++) 
  { 
    cout<<b[i]<<" "; 
  } 
  cout<<endl; 
 
  char c[10] = {'d','e','f','n','j','c','e','b','f','a'};//對字符數(shù)組排序 
  qSort(c, 0, 9); 
  for (i = 0; i < 10; i++) 
  { 
    cout<<c[i]<<" "; 
  } 
  cout<<endl; 
}//凡是可以用‘<'來比較大小的類型都可以排序了

201649145606285.jpg (430×98)