常見經(jīng)典排序算法

插入排序：
算法簡介：接插入排序(Insertion Sort)的基本思想是：每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中的適當位置，直到全部記錄插入完成為止。時間復(fù)雜度為O(n^2)。 最穩(wěn)定的排序算法但是效率很低
代碼實現(xiàn)：
void InsertSort(int *arr,int n)
{
                 for (int index = 0; index < n-1; ++index)
                {
                                 int end = index+1;
                                 int tmp = arr [end];
                                 while (end>0&&tmp<arr [end - 1])
                                {
                                                 arr[end] = arr [end - 1];
                                                end--;
                                }
                                 arr[end] = tmp;
                }
}
 
顯然當最小的數(shù)字在數(shù)組的最右端時，此時需要將整個數(shù)組進行移位，效率很低，而希爾排序可以有效的改善這個問題
希爾排序：希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩(wěn)定排序算法
       先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠?。r，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。
代碼實現(xiàn)：
void ShellSort(int *arr, int n)//希爾排序
{
                 int gap = n ;
                 while (gap>1)//由于gap=gap/3+1 最小值為1 則在gap=1時跳出循環(huán)
                {
                                gap = gap / 3 + 1; //{ 2, 8, 9, 6, 1, 3, 4, 5, 7, 0 ,-1,-2}//注意這里的＋1  當gap=1時此時排序等同于插入排序 但是由于之前將最小的數(shù)據(jù)已經(jīng)移到最左邊所以效率
//高于插入排序
                                 for (int index = 0; index <n-gap; ++index)
                                {
                                                 int end = index;
                                                 int tmp = arr [end+gap];
                                                 while (end>= 0 && arr [end]>tmp)                                                {
                                                                 arr[end+gap] = arr [end];
                                                                end -=gap;//此時插入間距為end
                                                }
                                                 arr[end+gap] = tmp;
                                }
                }
}
附注：上面希爾排序的步長選擇都是從n/3+1開始，每次再取上一次的三分之一加1，直到最后為1。關(guān)于希爾排序步長參見維基百科：http://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
冒泡排序：20世紀經(jīng)典算法之一，
原理是臨近的數(shù)字兩兩進行比較,按照從小到大或者從大到小的順序進行交換,這樣一趟過去后,最大或最小的數(shù)字被交換到了最后一位,再進行第二趟冒泡，由此我們可以寫出以下代碼：
void BubbleSort(int *arr, int n)
{
                 for (int i = 0; i < n; ++i)
                {
                                 for (int j = 0; j < n - i - 1; ++j)
                                {
                                                 if (arr [j]>arr[j + 1])
                                                                swap( arr[j], arr [j + 1]);
                                }
                }
}
這里我們設(shè)立一個標記變量 flag用來標記數(shù)列中的數(shù)是否在循環(huán)結(jié)束前就已經(jīng)排好序
代碼改進如下：
void BubbleSort(int *arr, int n)
{

                 bool flag = true ;
                 int k = n ;
                 while (flag)
                {
                                flag = false;
                                 for (int i = 1; i < k; ++i)
                                {
                                                 if (arr [i - 1]<arr[i])
                                                {
                                                                swap( arr[i - 1], arr [i]);
                                                                flag = true;//有發(fā)生交換 繼續(xù)冒泡 否則說明已經(jīng)有序
                                                }

                                }
                                k--;
                }

}
    如果這一趟發(fā)生了交換，這flag為rrue，則還需要繼續(xù)進行冒泡，否則說明數(shù)組已經(jīng)有序，后面的不必進行下去。
那么這里給出這樣一種情況：（2，1，3，4，5，6，7，8，9，10）第一次循環(huán)交換之后我們會發(fā)現(xiàn)，后面的數(shù)組已經(jīng)有序，不再需要我們進行冒泡，后面的操作都是不必要的 這里我們只需要記錄下最后一次進行交換的位置，那么下次遍歷只要遍歷到這個位置就可以結(jié)束。
代碼進一步優(yōu)化如下：
void BubbleSort(int *arr, int n)
{

                 int flag = n ;//第一次遍歷終點為數(shù)組尾
                 while (flag > 0)
                {
                                 int k = flag;
                                flag = 0;
                                 for (int j = 1; j < k; ++j)
                                {
                                                 if (arr [j - 1] > arr[j])
                                                {
                                                                swap( arr[j - 1], arr [j]);
                                                                flag = j;//后面的已經(jīng)排序好 記錄下下一次排序的終點
                                                }
                                }
                }
}
雖然有了這么多優(yōu)化，但是冒泡排序總體還是一種效率很低的排序，數(shù)據(jù)規(guī)模過大時不適合使用這種排序


堆排序：
堆的定義：
               1.堆是一顆完全二叉樹
               2.父結(jié)點總是大于或等于（小于或等于）任何一個子節(jié)點
               3每個結(jié)點的左子樹和右子樹都是一個二叉堆
               當父結(jié)點總是大于或等于任何一個子節(jié)點值時為最大堆。反之則為最小堆
堆的結(jié)構(gòu)示意圖如下：
存儲方式：
我們使用數(shù)組來存儲一個堆，可以看出設(shè)父節(jié)點下標值為i 其左孩子下標值為2*i+1,右孩子為2*1+2；
代碼實現(xiàn)如下：
void AdJust_down(int *arr, int parent, int size )
{
                 int child = 2 * parent +1;
                 while (child<size )
                {
                                 if (child+1<size &&arr[child+1]> arr[child])
                                {
                                                ++child;
                                }
                                 if (arr [parent]> arr[child])
                                                 break;
                                swap( arr[parent ], arr[child]);
                                 parent = child;
                                child = 2 * parent;
                }
}
void HeapSort(int *arr,int n)
{
                 for (int i = n/2-1; i >= 0; --i)
                {
                                AdJust_down( arr, i, n );
                }
                 for (int i = n - 1; i >= 1; --i)
                {
                                swap( arr[0], arr [i]);
                                AdJust_down( arr, 0, i);
                }
}
思路分析：
1.如果要對數(shù)字進行升序，我們首先首先將數(shù)組初始化為原始大堆
                 for (int i = n/2-1; i >= 0; --i)
                {
                                AdJust_down( arr, i, n );//從最后一個非葉子節(jié)點開始調(diào)整
                }
2.進行排序（以升序為例）
大堆的性質(zhì)為：最大的數(shù)據(jù)一定在堆頂將堆頂和堆最后一個元素進行交換，則最大的數(shù)字此時在數(shù)字尾部，再將堆頂元素下調(diào)，且堆的大小減1，知道堆大小為1循環(huán)結(jié)束，排序完成。
代碼如下：
                 for (int i = n - 1; i >= 1; --i)
                {
                                swap( arr[0], arr [i]);
                                AdJust_down( arr, 0, i);
                }

選擇排序
選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。 選擇排序是不穩(wěn)定的排序方法
為了減少比較的次數(shù)，我們一次遍歷同時選出最大值和最小值，代碼實現(xiàn)如下：
void SelectSort(int *arr, int n)
{
                
                 int i = 0, j = n - 1;
                 int max = j;
                 int min = i;
                 int left = 0; int right = n - 1;
                 while (left<=right)
                {
                                min = left;
                                max = right; ///?。。。。。。。。。?！重點
                                 for (i = left, j = right; i <= j; i++)
                                {
                                                 if (arr [min]>arr[i])
                                                                min = i;
                                                 if (arr [max] < arr[i]) ////{ 2, 9, 6, 1, 3, 4, 5, 7, 0 ,-8,1,-2}
                                                                max = i;
                                }
                                 if (left != min)
                                {
                                                swap( arr[left], arr [min]);
                                                 if (max == left)
                                                                max = min;
                                }
                                                
                                 if (right != max)
                                                swap( arr[right], arr [max]);
                                left++;
                                right--;
                }

}
這里我們必須注意到，以升序為例，如果一次遍歷找到的最大值剛好在數(shù)組左邊，此時肯定會先被移走，此時就最大值得下標就得更新為轉(zhuǎn)移后的位置


快速排序：
該方法的基本思想是：
1．先從數(shù)列中取出一個數(shù)作為key。
2．分區(qū)過程，將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。
3．再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(shù)。
代碼實現(xiàn)如下：
int PartSort(int *arr, int left, int right)
{
                 int key = arr [right]; //{ 10,2, 8, 9, 6, 1, 3, 4, 5, 7, 0 ,-1,-2,-100};
                 int begin = left ;
                 int end = right - 1;
                 while (begin<end)
                {
                                 while (begin<end&&arr [begin]<=key)
                                {
                                                begin++;
                                }
                                 while (begin<end&&arr [end]>=key)
                                {
                                                end--;
                                }
                                 if (begin < end)
                                                swap( arr[begin], arr [end]);
                }
                 if (arr [begin]>arr[right])
                {
                                swap( arr[begin], arr [right]);
                                 return begin;
                }
                 return right ;

}
void QuickSort(int *arr, int left,int right)
{              
                 if (left >= right)
                                 return;
                 int div = PartSort(arr , left, right);
                QuickSort( arr, div + 1, right );
                QuickSort( arr, left , div - 1);

}