C語言實現(xiàn)選擇排序、冒泡排序和快速排序的代碼示例
更新時間：2016年04月09日 14:56:10 作者：hzy3774
這篇文章主要介紹了C++中實現(xiàn)選擇排序、冒泡排序和快速排序的代碼示例,例子帶有執(zhí)行時間統(tǒng)計還可以簡單看一下效率對比,需要的朋友可以參考下
選擇和冒泡
#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 ++)//排在后的是已經排序的
{
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 ++)//前面的實排好的
{
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;//記錄最右元素索引
//默認中值是左值，現(xiàn)在要把凡是比中值大的元素放到中值左邊
while(right > mid){//因此從右開始向中值遍歷，到達中值時遍歷結束
if (a[right] < a[mid])//如果右值比中值還小，說明他不該在右邊，要把它放到左邊
{
temp = a[mid];//所以先把中值的地盤騰出來
a[mid] = a[right];//把比中值小的那個數(shù)放在那兒
//中值沒地方放，必須右移移位，但是直接右移會覆蓋原來他右邊的那個值
a[right] = a[++mid];//不過right索引的空間已經騰出來了，就把中值原來右邊的值放到right
a[mid] = temp;//然后就可以把mid右移一位
}
else{
right--;//否則的話說明right已然大于等于mid，不用移動，繼續(xù)判斷right左邊那個數(shù)
}
}//這樣right與mid重合之時，退出循環(huán)，此時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){//選擇排序，參數(shù)是數(shù)組名和元素個數(shù)
int i, j, m, temp;
for (i = 0; i < len - 1; i++)//從開始到倒數(shù)第二個元素
{
m = i;//先記錄最左邊的元素索引，假設他為最小
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++)//從頭遍歷到已序隊列往前第二個
{
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ù)組排序是否已經正確
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();//產生隨機數(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;//計算排序時間
printf("...\t排序用時 %lf 秒 ", cost);//輸出排序所用時間
if (checkSorted(a, 99999))//檢查排序是否正確
{
printf("正確!\n");
}else{
printf("有錯!\n");
}
Sleep(1200);//暫停一下，使每次時間種子不同
}
}
1. 快速排序的結果：
99999個隨機數(shù)一般不超過0.05秒，很快
2.選擇法排序結果：
99999個隨機數(shù)一般不超過0.05秒，很快
2.選擇法排序結果：
一般在20多秒；
3.冒泡法，一般情況下交換的次數(shù)會很多，結果：
排序時間一般在50秒左右，最慢。
在C++中，還可以定義函數(shù)模板
因為快速排序通常很快，所以用它來對不同的數(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);//對浮點數(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;
}//凡是可以用‘<'來比較大小的類型都可以排序了
相關文章
這篇文章主要為大家詳細介紹了C語言合并兩個帶頭節(jié)點升序排列鏈表的方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-03-03
通常靜態(tài)數(shù)據(jù)成員在類聲明中聲明,在包含類方法的文件中初始化.初始化時使用作用域操作符來指出靜態(tài)成員所屬的類.但如果靜態(tài)成員是整型或是枚舉型const,則可以在類聲明中初始化2013-09-09
shared_ptr是一個標準的共享所有權的智能指針，允許多個指針指向同一個對象，定義在memory文件中，命名空間為std，這篇文章主要介紹了C++ shared_ptr使用，需要的朋友可以參考下2022-11-11
埃拉托斯特尼篩法，簡稱埃氏篩或愛氏篩，是一種由希臘數(shù)學家埃拉托斯特尼所提出的一種簡單檢定素數(shù)的算法。本文將利用這一算法實現(xiàn)求解素數(shù)，感興趣的可以了解一下2023-01-01
詳解C++值多態(tài)中的傳統(tǒng)多態(tài)與類型擦除
值多態(tài)是一種介于傳統(tǒng)多態(tài)與類型擦除之間的多態(tài)實現(xiàn)方式，借鑒了值語義，保留了繼承，在單繼承的適用范圍內，程序和程序員都能從中受益。這篇文章主要介紹了C++值多態(tài)中的傳統(tǒng)多態(tài)與類型擦除,需要的朋友可以參考下2020-04-04
這篇文章主要介紹了qt實現(xiàn)倒計時示例,需要的朋友可以參考下2014-05-05
C++入門教程之內聯(lián)函數(shù)與extern?"C"詳解
C++中的內聯(lián)函數(shù)與靜態(tài)函數(shù)靜態(tài)函數(shù)靜態(tài)函數(shù)的定義靜態(tài)函數(shù)又稱為內部函數(shù),下面這篇文章主要給大家介紹了關于C++入門教程之內聯(lián)函數(shù)與extern?"C"的相關資料,需要的朋友可以參考下2023-01-01
這篇文章主要為大家詳細介紹了C語言實現(xiàn)銀行管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01
這篇文章主要為大家介紹了C語言的const,指針和引用，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
首先，移動語義和完美轉發(fā)這兩個概念是在C++的模板編程的基礎上，新增的特性，主要是配合模板來使用。本篇會從C++的值類型，到移動拷貝與移動賦值來理解移動語義與完美轉發(fā)2022-09-09