淺析排序算法

楊玉芹

摘要：本文主要關于4種排序進行了一個簡單的講解，并為每一種排序使用C/C++語言給每種排序算法相應的實現，并在最后比較了每種算法的穩定性以及時間復雜度.看本文的前提是熟悉C/C++程序設計語言。

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

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

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

2冒泡排序

冒泡排序，是一種計算機科學領域的較簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。

算法用C語言的實現如下：

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

3插入排序

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

插入排序有直接插入排序，折半插入排序，2-路插入排序和希爾排序。這里僅給出直接插入排序的實現。

算法用C++語言的實現如下：

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快速排序

快速排序的基本思想是，通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄關鍵字均比另一部分記錄的關鍵字小，則可分為對這兩部分繼續進行排序，已達到整個序列有序。

算法用C語言的實現如下：

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選擇排序

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

算法用C語言的實現如下：

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

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

穩定性 穩定 穩定 穩定 不穩定

時間復雜度 O(n^2) O(n^2) O(n^2) O(n^2)

[參考文獻]

[1]嚴蔚敏,吳偉民,編著.數據結構（C語言版）.清華大學出版社,2011年5月.

[2]鄧俊輝,編著.數據結構（C++語言版）（第二版）.清華大學出版社，2011年10月.

[3]Mark Allen Weiss,著.數據結構與算法分析——C語言描述.機械工業出版社，2011年10月.

[4]百度百科知識.