排序算法之插入排序、冒泡排序和選擇排序

　　将這三個排序放在一起的原因是在輸入資料無序或者随機性較大的情況下，三種排序的時間複雜度都是O(n^2)，下面将依次介紹這三種排序方法

1、插入排序

　　所謂插入排序，就相當于将未排序的序列分為兩部分，第一部分是已經有序的（初試狀态下，第一部分隻包含第一個元素，它肯定是有序的），第二部分是無序的，順序周遊第二部分，将其插入到第一部分中合适的位置

　　是以，插入排序需要兩個主要步驟，第一個就是維持有序部分，第二個就是周遊無序序列并插入元素（插入過程中涉及到元素的移動）

　　代碼如下：

　　

#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
void insertSort(int data[],int length){
    if(data==NULL||length<=0)
        return ;
    for(int i=1;i<length;i++){   //周遊無序的第二部分
        int cur=data[i];     //記錄目前的值，因為如果需要将該值插入到前面的有序部分，需要将該值前面的部分後移一位
        if(data[i-1]>cur){   //如果目前元素的值比它前面的值小，則需要插入操作，否則不需要
            int j=i-1
            for(;j>=0&&data[j]>cur;j--)  //找到對應的插入位置
                data[j+1]=data[j];    //移動元素
            data[j+1]=cur;            //插入目前值
        }
    }
}
int main(){
    int data[]={9,5,6,4,1,2,3,7,8,1};
    int length=sizeof(data)/sizeof(int);
    insertSort(data,length);
    copy(data,data+length,ostream_iterator<int>(cout,","));
    return 0;
}      

　　插入排序的時間複雜度分析：試想，如果數組本來有序，則第一層循環中的插入操作沒有執行，整個排序過程隻是周遊了一下數組，是以插入排序在數組有序的情況下，時間複雜度是O(n)，當數組逆序的時候，第二部分的每一個數組都需要向前插入，時間複雜度是O(n^2)，在平均情況下，時間複雜度也是O(n^2)

　　插入排序的穩定性：由插入排序的過程可以知道，插入排序是穩定的

　　總結：插入排序的時間複雜度原始數組有關系，最差和平均時間複雜度是O(n^2)，最優情況下是O(n)，插入排序是穩定的排序

2、冒泡排序

　　冒泡排序的過程就像水中的氣泡逐漸向上升的過程，深度越大的氣泡越小，我們從最上面的氣泡開始考慮，如果目前氣泡小于它下面的氣泡，則交換兩個氣泡的位置，這個過程依次向下執行，這樣的一組比較過程稱為一趟排序，經過一趟排序，總是有一個數組元素到達它應該在的位置上，是以，假設數組共有n個元素，則經曆n-1趟排序就可使數組有序。

#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
void bubbleSort(int data[],int length){
    if(data==NULL||length<=0)
        return ;
    for(int i=0;i<length-1;i++){    //n-1趟排序過程
        bool flag=false;                //用來記錄一趟排序中，數組元素是否進行了交換
        for(int j=length-1;j>i;j--){  //後到前依次比較
            if(data[j-1]>data[j]){
                swap(data[j],data[j-1]);
                flag=true;
            }
        }
        if(flag==false)
            return ;
    }
}
int main(){
    int data[]={6,9,5,4,5,6,2,1,3};
    int length=sizeof(data)/sizeof(int);
    bubbleSort(data,length);
    copy(data,data+length,ostream_iterator<int>(cout,","));
    return 0;
}      

　　冒泡排序的時間複雜度分析：由上面的代碼可知，在一趟排序中，内循環執行了n-1次比較，如果數組有序，則交換的次數為0，函數退出，是以冒泡的最佳時間複雜度是O(n)，如果數組逆序，每趟排序都需要（j-i）次交換，是以最壞的時間複雜度是O(n^2)，平均時間複雜度也是O(n^2)

　　冒泡排序的穩定性：由于是從上到下依次比較，是以，如果兩個數相同，它們在原始數組中的相對位置和排序過後的相對位置應該不變，是以冒泡排序是穩定的排序

　　總結：冒泡排序的時間複雜度和輸入數組有關系，如果有序，則有最佳時間複雜度O(n)，它的平均和最差時間複雜度是O(n^2)，冒泡排序是穩定的排序

3、選擇排序

　　選擇排序，顧名思義，就是每次從數組選擇出最小的數字放置在數組中，是這三種排序中最簡單的一種排序方法

　　代碼如下所示：

#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
void selectSort(int data[],int length){
    if(data==NULL||length<=0)
        return ;
    for(int i=0;i<length-1;i++){
        int min=i;
        for(int j=i;j<length;j++){
            if(data[j]<data[min])
                min=j;
        }
        if(min!=i)
            swap(data[i],data[min]);
    }
}
int main(){
    int data[]={9,5,4,6,1,2,3,10,7,8};
    int length=sizeof(data)/sizeof(int);
    selectSort(data,length);
    copy(data,data+length,ostream_iterator<int>(cout,","));
    return 0;
}      

　　選擇排序的時間複雜度分析：要排序n個數，隻需要進行n-1次選擇即可，但是每一次的選擇過程都需要從目前位置的下一位置周遊到最後，是以選擇排序的時間複雜度是O(n^2)

　　選擇排序的穩定性：由于每次選擇都需要進行周遊數組，在原始數組中兩個相同的數字A、B，在選擇時B可能會先于A被選擇，是以選擇排序不是穩定的排序

　　總結：選擇排序和輸入數組沒有關系，它的時間複雜度總是O(n^2)，選擇排序是不穩定的排序。