經(jīng)典排序算法與STL

排序算法

按照是否將元素放入到內(nèi)存中，排序分為內(nèi)部排序和外部排序啸胧。內(nèi)部排序適合元素不多的文件探赫，按照元素的排序原則，內(nèi)部排序分為：

插入排序
交換排序
選擇排序
歸并排序

插入排序

基本方法是：尋找一個(gè)指定元素在待排序元素中的位置，然后將它插入

直接插入

基本思想：每次將一個(gè)待排序的元素按其關(guān)鍵碼的大小插入到一個(gè)已經(jīng)排好序的有序序列中，知道全部元素排序好。

void insert_sort(int arr[], int len){
 for (int i=1; i<len; i++) {
    int temp = arr[i] ;
    for (int j = i-1; j>=0; j--) {
      //j+1位置一直是空的菇绵，
        if (arr[j]>temp) {
            arr[j+1] = arr[j] ;
        }else {
            arr[j+1] = temp ;
            break ;
        }
    }
    
  }

 }

直接插入的兩個(gè)特點(diǎn)：基本有序的序列，直接插入最快镇眷。記錄個(gè)數(shù)很少的無(wú)序序列咬最，直接插入也很快

希爾排序

希爾排序是對(duì)直接插入排序的一種改進(jìn)。它的基本思想是：將待排序的元素分成多個(gè)子集欠动，分別對(duì)這些子集進(jìn)行直接插入排序永乌，待整個(gè)序列都有序時(shí)，再對(duì)元素進(jìn)行一次直接插入排序具伍。

void Sort::shell_sort(int arr[] ,int len) {
//增長(zhǎng)區(qū)間
for (int d = len /2; d>=1; d = d/2)
{   //一次希爾排序
    for (int i = d; i < len; i++)
    {    //和有序的數(shù)組的最后一個(gè)元素比較
        if (arr[i]<arr[i-d])
        {
            int temp = arr[i] ;
            int j = i-d ;
            while(j>=0&&arr[j]>temp){
                arr[j+d] = arr[j];
                j = j-d;
            }
            arr[j+d] = temp ;
        }
    }
}

}

交換排序

交換排序的基本方法是：在待排序的元素中選擇兩個(gè)元素铆遭，將他們的關(guān)鍵碼進(jìn)行比較，進(jìn)行排序沿猜。

冒泡排序

基本思想是：兩兩比較相鄰的元素枚荣，如果反序，則交換位置啼肩，直到?jīng)]有反序的元素為止橄妆。

void bubble_sort(int arr[], int len){
//從小到大
for (int i = 0; i<len; i++) {
    for (int j = len-1; j>i; j--) {
        if (arr[j]<arr[j-1]) {
            int temp = arr[j] ;
            arr[j] = arr[j-1] ;
            arr[j-1] = temp ;
        }
    }
}    
}

快速排序

快速排序是冒泡排序的改進(jìn)算法衙伶，快速排序元素的比較設(shè)移動(dòng)是序列的兩端到中間進(jìn)行的。它的基本思想是：
在分區(qū)中選擇一個(gè)元素為軸值害碾，將待排序的元素劃分為兩個(gè)分區(qū)矢劲，左側(cè)元素的關(guān)鍵碼都小于或者等于軸值，右側(cè)元素的關(guān)鍵碼的值都大于或者等于軸值慌随。重復(fù)上述過(guò)程芬沉，直到整個(gè)序列有序。

void quick_sort(int arr[], int left, int right){
//遞歸結(jié)束條件
if (left<right) {
    //一次遍歷
    int i = left , j = right , key = arr[left] ;
     while (i<j) {
        while (i<j&&arr[j]>key) 
        j-- ;
        if (i<j)
        arr[i++] =arr[j];
        while (i<j&& arr[i]<key)
        i++ ;
        if (i<j) 
        arr[j--] = arr[i] ; 
     }
    //遞歸
    arr[i]=key ;
    quick_sort(arr, left, i-1);
    quick_sort(arr, i+1, right); 
}

}

選擇排序

選擇排序的基本思想是：每趟排序在待排序列表中選擇關(guān)鍵碼最小的元素阁猜，順序添加到已將排序好的有序序列中去丸逸，直到全部記錄都排序完成

簡(jiǎn)單選擇排序

簡(jiǎn)單選擇排序的基本思想是：每趟在待排序的序列中找出最小的記錄加到序列頭部。直到都排序完成剃袍。

void select_sort(int arr[], int len){
for (int i= 0; i<len-1; i++) {
        int temp = i ;
    for (int j=i+1; j<len; j++) {
        if(arr[j]<arr[temp]){
            temp = j ;
        }
    }
    if (temp != i) {
        int arrTemp = arr[i] ;
        arr[i] = arr[temp] ;
        arr[temp] =arrTemp ;
    }
}
}

堆排序

堆排序是對(duì)簡(jiǎn)單選擇排序的改進(jìn)黄刚。堆排序利用了前一趟比較的結(jié)果，減小了比較的次數(shù)民效，從而提高整個(gè)排序的效率憔维。

//調(diào)整堆
void Sort::heap_adjust(int arr[], int i, int len){
int child = 2 * i + 1;
int temp;
while (child<len) {
 // 得到子結(jié)點(diǎn)中鍵值較大的結(jié)點(diǎn) 這里求的是大根堆, 如果是小根堆，下面變?yōu)閍rr[child + 1] < arr[child]
    if (child < len - 1 && arr[child + 1]>arr[child])
        child ++;
    //這里求的是大根堆畏邢，如果求小根堆a(bǔ)rr[i] > arr[child]
    if (arr[i] <arr[child])
    {
        temp = arr[i];
        arr[i] = arr[child];
        arr[child] = temp;
        i =child ;
        child = 2 * i + 1;
    }
    else
        break;
}   
}

//堆排序
void Sort::heap_sort(int arr[], int len){
int i;
// 調(diào)整序列的前半部分元素业扒，調(diào)整完之后第一個(gè)元素是序列的最大的元素
for (int i = len / 2 - 1; i >= 0; i--)
{
    heap_adjust(arr, i, len);
}

for (i = len - 1; i > 0; i--)
{
    int temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    // 不斷縮小調(diào)整heap的范圍，每一次調(diào)整完畢保證第一個(gè)元素是當(dāng)前序列的最大值
    heap_adjust(arr, 0, i);
}

}

歸并排序

歸并排序的基本思想方法是：將兩個(gè)或者兩個(gè)以上的有序序列歸并成一個(gè)有序序列

void merge(int arr[], int temp_arr[], int start_index, int mid_index, int end_index){
int i=start_index;
int k=0;
int j=mid_index+1 ;

//直到一個(gè)組數(shù)被遍歷完
while (i<mid_index+1 && j<1+end_index) {
    if (arr[i]>arr[j]) {
        temp_arr[k++] =arr[j++];
    }else{
        temp_arr[k++] =arr[i++];
    }
}
//將沒(méi)被遍歷完的數(shù)組添加到數(shù)組中去
while (i<1+mid_index) {
    temp_arr[k++]= arr[i++];
}

while (j<1+end_index) {
    temp_arr[k++] =arr[j++];
}

for (i = 0, j = start_index; j <1+end_index; i ++, j ++)
     arr[j] = temp_arr[i];
}

void merge_sort(int arr[], int arr_temp[],int start_index, int end_index){
if (start_index<end_index) {
    int mid = (start_index+end_index)/2 ;
    merge_sort(arr, arr_temp, start_index, mid);
    merge_sort(arr, arr_temp, mid+1, end_index);
    merge(arr, arr_temp, start_index, mid, end_index);
}

排序的比較

排序方法 | 平均復(fù)雜度 | 空間復(fù)雜度 | 穩(wěn)定性
------------ | ------------- | ------------
直接插入排序 | O(n²)| O(1) | 穩(wěn)定
希爾排序 | O(nlog₂n) | O(1) |不穩(wěn)定
冒泡排序 | O(n²)|O(1)|穩(wěn)定
快速排序 | O(nlog₂n) | O(nlog₂n)|不穩(wěn)定
簡(jiǎn)單選擇排序 | O(n²) | O(1)| 穩(wěn)定
堆排序 | O(nlog₂n) | O(1)| 不穩(wěn)定
歸并排序 | O(nlog₂n) | O(n)| 穩(wěn)定

STL中相關(guān)排序算法

所有STL sort算法函數(shù)的名字列表:

函數(shù)名	功能描述
sort	對(duì)給定區(qū)間所有元素進(jìn)行排序
stable_sort	對(duì)給定區(qū)間所有元素進(jìn)行穩(wěn)定排序
partial_sort	對(duì)給定區(qū)間所有元素部分排序
partial_sort_copy	對(duì)給定區(qū)間復(fù)制并排序
nth_element	找出給定區(qū)間的某個(gè)位置對(duì)應(yīng)的元素
is_sorted	判斷一個(gè)區(qū)間是否已經(jīng)排好序
partition	使得符合某個(gè)條件的元素放在前面
stable_partition	相對(duì)穩(wěn)定的使得符合某個(gè)條件的元素放在前面

比較函數(shù)：

當(dāng)你需要按照某種特定方式進(jìn)行排序時(shí)舒萎，你需要給sort指定比較函數(shù)程储，否則程序會(huì)自動(dòng)提供給你一個(gè)比較函數(shù)

vector < int > vect;

sort(vect.begin(), vect.end());//此時(shí)相當(dāng)于調(diào)用

sort(vect.begin(), vect.end(), less<int>() );

sort 中的其他比較函數(shù)

equal_to	相等
not_equal_to	不相等
less	小于
greater	大于
less_equal	小于等于
greater_equal	大于等于

上述例子中系統(tǒng)自己為sort提供了less仿函數(shù)。在STL中還提供了其他仿函數(shù)逆甜，以下是仿函數(shù)列表: 不能直接寫(xiě)入仿函數(shù)的名字虱肄，而是要寫(xiě)其重載的()函數(shù)： less<int>();
當(dāng)你的容器中元素時(shí)一些標(biāo)準(zhǔn)類型（int float char)或者string時(shí)致板，你可以直接使用這些函數(shù)模板交煞。但如果你時(shí)自己定義的類型或者你需要按照其他方式排序，你可以有兩種方法來(lái)達(dá)到效果：一種是自己寫(xiě)比較函數(shù)斟或。另一種是重載類型的'<'操作賦素征。

全排序：

全排序即把所給定范圍所有的元素按照大小關(guān)系順序排列。sort采用的是成熟的"快速排序算法"(目前大部分STL版本已經(jīng)不是采用簡(jiǎn)單的快速排序萝挤，而是結(jié)合內(nèi)插排序算法)御毅。復(fù)雜度為nlog₂n。stable_sort采用的是"歸并排序"怜珍，分派足夠內(nèi)存時(shí)端蛆，其算法復(fù)雜度為nlog₂n, 否則其復(fù)雜度為nlog₂n*log₂n，其優(yōu)點(diǎn)是會(huì)保持相等元素之間的相對(duì)位置在排序前后保持一致酥泛。

用于全排序的函數(shù)有：

void sort(RandomAccessIterator first, RandomAccessIterator last);
void sort(RandomAccessIterator first, RandomAccessIterator last,StrictWeakOrdering comp);
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);

局部排序：

partial_sort采用的堆排序（heapsort）今豆，它在任何情況下的復(fù)雜度都是nlog₂n嫌拣。

局部排序其實(shí)是為了減少不必要的操作而提供的排序方式。

其函數(shù)原型為：

void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last);
void partial_sort(RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last, StrictWeakOrdering comp);
RandomAccessIterator partial_sort_copy(InputIterator first, InputIteratorlast,RandomAccessIteratorresult_first,RandomAccessIterator result_last);
RandomAccessIterator partial_sort_copy(InputIterator first, InputIteratorlast,RandomAccessIteratorresult_first,RandomAccessIterator result_last, Compare comp);

例如：班上有1000個(gè)學(xué)生呆躲，我想知道分?jǐn)?shù)最低的5名是哪些人异逐。
partial_sort(vect.begin(),vect.begin()+5,vect.end(),less<student>());

nth_element 指定元素排序

void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,RandomAccessIterator last,StrictWeakOrdering comp);

例如：班上有1000個(gè)學(xué)生，我想知道分?jǐn)?shù)排在倒數(shù)第4名的學(xué)生插掂。
nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());

partition 和stable_partition

partition就是把一個(gè)區(qū)間中的元素按照某個(gè)條件分成兩類灰瞻，并沒(méi)有排序。