楊玉芹

摘要：本文主要關(guān)于4種排序進(jìn)行了一個(gè)簡單的講解，并為每一種排序使用C/C++語言給每種排序算法相應(yīng)的實(shí)現(xiàn)，并在最后比較了每種算法的穩(wěn)定性以及時(shí)間復(fù)雜度.看本文的前提是熟悉C/C++程序設(shè)計(jì)語言。

關(guān)鍵詞：排序；冒泡算法；插入排序；快速排序；選擇排序1引言

隨著計(jì)算機(jī)的不斷普及，技術(shù)越來越成熟，計(jì)算機(jī)硬件以及存儲設(shè)備具有局限性，提供計(jì)算機(jī)的效率成了程序員特別關(guān)注的一方向，其中排序就是其中之一。如何能在最短時(shí)間，在最節(jié)省內(nèi)存的情況下，使呈任意序列的數(shù)據(jù)元素，在最快的時(shí)間得到從大到小或從小到大的序列，是程序員一直研究的問題。

本文主要是簡單的講述一下排序的幾種算法，冒泡排序，插入排序，快速排序，選擇排序。

2冒泡排序

冒泡排序，是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。

算法用C語言的實(shí)現(xiàn)如下：

for(int i=0;i<10;i++){for(int j=i;j<10;j++){if(a[j]

3插入排序

插入排序的思路簡要的描述是：將序列的元素分作有序和無序兩類，然后在保持前一類有序的前提下，通過迭代將后一類元素逐一插至前一類中的適當(dāng)位置。

插入排序有直接插入排序，折半插入排序，2-路插入排序和希爾排序。這里僅給出直接插入排序的實(shí)現(xiàn)。

算法用C++語言的實(shí)現(xiàn)如下：

void InsertSort(int*p,int n){int temp=0;for(int i=1;ip[i-1]){temp=p[i];p[i]=p[i-1];for(int j=i-2;temp>p[j]&&j>0;j--){p[j+1]=p[j];}p[j+1]=temp;}}}

4快速排序

快速排序的基本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分為對這兩部分繼續(xù)進(jìn)行排序，已達(dá)到整個(gè)序列有序。

算法用C語言的實(shí)現(xiàn)如下：

int QuickSock(int*a,int Left,int Right)//算法的核心

{int Temp=a[Left];while(Left=a[Right])

{Right--;}a[Left]=a[Right];while(Left

a[Right]=a[Left];}a[Left]=Temp; return Right;}

void Repeat(int*a,int Left,int Right)

{if(Left

5選擇排序

選擇排序的基本思想是，每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。

算法用C語言的實(shí)現(xiàn)如下：

void SelectSort(int*p,int n){int j=0;int temp=0;for(int k=n;k>0;k--){

for(int i=0;i

int SelectMinKey(int*q,int m){int temp =q[0];int min=0;for(int i=1;i<=m;i++)

{if(temp>q[i])temp=q[i];min=i;}}return min;}

6對比各種排序

表1

冒泡排序 插入排序 快速排序 選擇排序

穩(wěn)定性 穩(wěn)定 穩(wěn)定 穩(wěn)定 不穩(wěn)定

時(shí)間復(fù)雜度 O(n^2) O(n^2) O(n^2) O(n^2)

[參考文獻(xiàn)]

[1]嚴(yán)蔚敏,吳偉民,編著.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社,2011年5月.

[2]鄧俊輝,編著.數(shù)據(jù)結(jié)構(gòu)（C++語言版）（第二版）.清華大學(xué)出版社，2011年10月.

[3]Mark Allen Weiss,著.數(shù)據(jù)結(jié)構(gòu)與算法分析——C語言描述.機(jī)械工業(yè)出版社，2011年10月.

[4]百度百科知識.