欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

詳細總結C++的排序算法

 更新時間:2016年07月20日 09:22:42   投稿:daisy  
趁空閑時間,小編決定把C++的排序算法分析并總結下,以便溫故知新。也方便需要的朋友可以參考學習。

排序算法經(jīng)過了很長時間的演變,產(chǎn)生了很多種不同的方法。對于初學者來說,對它們進行整理便于理解記憶顯得很重要。每種算法都有它特定的使用場合,很難通用。因此,我們很有必要對所有常見的排序算法進行歸納。

我不喜歡死記硬背,我更偏向于弄清來龍去脈,理解性地記憶。比如下面這張時間復雜度圖,我們將圍繞這張圖來分析。

上面的這張圖來自一個PPT。它概括了數(shù)據(jù)結構中的所有常見的排序算法,給大家總結如下。

區(qū)分穩(wěn)定與不穩(wěn)定:快速、希爾、堆、選擇不穩(wěn)定,其他排序算法均穩(wěn)定。

平均時間復雜度:冒泡,選擇,插入是O(n2),其他均是O(n*log2n)

最壞時間復雜度:冒泡,選擇,插入,快排是O(n2),其他是O(n*log2n)

平均和最壞時間復雜度:只有O(n2)和O(n*log2n)兩種,冒泡,選擇,插入是O(n2),最壞情況下加一個快排,其他均是O(nlog2n)。

一、直接插入排序(插入排序)。

     1、算法的偽代碼(這樣便于理解):    

   INSERTION-SORT (A, n)       A[1 . . n] 
   for j ←2 to n 
     do key ← A[ j] 
     i ← j – 1 
     while i > 0 and A[i] > key 
        do A[i+1] ← A[i] 
          i ← i – 1 
     A[i+1] = key

     2、思想:如下圖所示,每次選擇一個元素K插入到之前已排好序的部分A[1…i]中,插入過程中K依次由后向前與A[1…i]中的元素進行比較。若發(fā)現(xiàn)發(fā)現(xiàn)A[x]>=K,則將K插入到A[x]的后面,插入前需要移動元素。

     3、算法時間復雜度。  

        最好的情況下:正序有序(從小到大),這樣只需要比較n次,不需要移動。因此時間復雜度為O(n)  

        最壞的情況下:逆序有序,這樣每一個元素就需要比較n次,共有n個元素,因此實際復雜度為O(n­2)  

       平均情況下:O(n­2)

     4、穩(wěn)定性。  

     理解性記憶比死記硬背要好。因此,我們來分析下。穩(wěn)定性,就是有兩個相同的元素,排序先后的相對位置是否變化,主要用在排序時有多個排序規(guī)則的情況下。在插入排序中,K1是已排序部分中的元素,當K2和K1比較時,直接插到K1的后面(沒有必要插到K1的前面,這樣做還需要移動??!),因此,插入排序是穩(wěn)定的。

二、希爾排序(插入排序)

     1、思想:希爾排序也是一種插入排序方法,實際上是一種分組插入方法。先取定一個小于n的整數(shù)d1作為第一個增量,把表的全部記錄分成d1個組,所有距離為d1的倍數(shù)的記錄放在同一個組中,在各組內(nèi)進行直接插入排序;然后,取第二個增量d2(<d1),重復上述的分組和排序,直至所取的增量dt=1

     例如:將 n 個記錄分成 d 個子序列: 

       { R[0],   R[d],     R[2d],…,     R[kd] } 
       { R[1],   R[1+d], R[1+2d],…,R[1+kd] }
         …
       { R[d-1],R[2d-1],R[3d-1],…,R[(k+1)d-1] }

    

     說明:d=5 時,先從A[d]開始向前插入,判斷A[d-d],然后A[d+1]與A[(d+1)-d]比較,如此類推,這一回合后將原序列分為d個組。<由后向前>

     2、時間復雜度。  

     最好情況:由于希爾排序的好壞和步長d的選擇有很多關系,因此,目前還沒有得出最好的步長如何選擇(現(xiàn)在有些比較好的選擇了,但不確定是否是最好的)。所以,不知道最好的情況下的算法時間復雜度。  

     最壞情況下:O(N*logN),最壞的情況下和平均情況下差不多。  

     平均情況下:O(N*logN)

     3、穩(wěn)定性。  

     由于多次插入排序,我們知道一次插入排序是穩(wěn)定的,不會改變相同元素的相對順序,但在不同的插入排序過程中,相同的元素可能在各自的插入排序中移動,最后其穩(wěn)定性就會被打亂,所以shell排序是不穩(wěn)定的。(有個猜測,方便記憶:一般來說,若存在不相鄰元素間交換,則很可能是不穩(wěn)定的排序。)

三、冒泡排序(交換排序)

       1、基本思想:通過無序區(qū)中相鄰記錄關鍵字間的比較和位置的交換,使關鍵字最小的記錄如氣泡一般逐漸往上“漂浮”直至“水面”。

       

      2、時間復雜度  

      最好情況下:正序有序,則只需要比較n次。故,為O(n)  

      最壞情況下:  逆序有序,則需要比較(n-1)+(n-2)+……+1,故,為O(N*N)

      3、穩(wěn)定性  
      排序過程中只交換相鄰兩個元素的位置。因此,當兩個數(shù)相等時,是沒必要交換兩個數(shù)的位置的。所以,它們的相對位置并沒有改變,冒泡排序算法是穩(wěn)定的!

四、快速排序(交換排序)
     1、思想:它是由冒泡排序改進而來的。在待排序的n個記錄中任取一個記錄(通常取第一個記錄),把該記錄放入適當位置后,數(shù)據(jù)序列被此記錄劃分成兩部分。所有關鍵字比該記錄關鍵字小的記錄放置在前一部分,所有比它大的記錄放置在后一部分,并把該記錄排在這兩部分的中間(稱為該記錄歸位),這個過程稱作一趟快速排序。

     2、算法復雜度  

      最好的情況下:因為每次都將序列分為兩個部分(一般二分都復雜度都和logN相關),故為 O(N*logN)  

      最壞的情況下:基本有序時,退化為冒泡排序,幾乎要比較N*N次,故為O(N*N)

      3、穩(wěn)定性  

      由于每次都需要和中軸元素交換,因此原來的順序就可能被打亂。如序列為 5 3 3 4 3 8 9 10 11會將3的順序打亂。所以說,快速排序是不穩(wěn)定的!

五、直接選擇排序(選擇排序)

      1、思想:首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再從剩余未排序元素中繼續(xù)尋找最小元素,然后放到排序序列末尾。以此類推,直到所有元素均排序完畢。具體做法是:選擇最小的元素與未排序部分的首部交換,使得序列的前面為有序。  

      2、時間復雜度。 

      最好情況下:交換0次,但是每次都要找到最小的元素,因此大約必須遍歷N*N次,因此為O(N*N)。減少了交換次數(shù)! 

      最壞情況下,平均情況下:O(N*N)

      3、穩(wěn)定性 

      由于每次都是選取未排序序列A中的最小元素x與A中的第一個元素交換,因此跨距離了,很可能破壞了元素間的相對位置,因此選擇排序是不穩(wěn)定的!

六、堆排序

     1、思想:利用完全二叉樹中雙親節(jié)點和孩子節(jié)點之間的內(nèi)在關系,在當前無序區(qū)中選擇關鍵字最大(或者最小)的記錄。也就是說,以最小堆為例,根節(jié)點為最小元素,較大的節(jié)點偏向于分布在堆底附近。 

      2、算法復雜度 

         最壞情況下,接近于最差情況下:O(N*logN),因此它是一種效果不錯的排序算法。

      3、穩(wěn)定性 

         堆排序需要不斷地調(diào)整堆,因此它是一種不穩(wěn)定的排序!

七、歸并排序

      1、思想:多次將兩個或兩個以上的有序表合并成一個新的有序表。

       2、算法時間復雜度 

          最好的情況下:一趟歸并需要n次,總共需要logN次,因此為O(N*logN)  

         最壞的情況下,接近于平均情況下,為O(N*logN) 

          說明:對長度為n的文件,需進行l(wèi)ogN 趟二路歸并,每趟歸并的時間為O(n),故其時間復雜度無論是在最好情況下還是在最壞情況下均是O(nlgn)。

      3、穩(wěn)定性 
         歸并排序最大的特色就是它是一種穩(wěn)定的排序算法。歸并過程中是不會改變元素的相對位置的。 
      4、缺點是,它需要O(n)的額外空間。但是很適合于多鏈表排序。 
 

5、C++實現(xiàn)排序算法代碼總結如下:

復制代碼 代碼如下:

#include<iostream>
#include<vector>
#include<limits>
using namespace std;
//插入排序,相當于打牌,相當于把一個值插入到已經(jīng)排序好的一個數(shù)組中,
//先把待排序的值放到一個臨時變量里面,讓排好序的數(shù)字從大到小去與這個值做比較,若大于就把位置往后挪一個,
//騰出一個空位置出來,找到第一個小于他的位置就在該位置后面插入此值,因為是原地排序,所以待排序的值也在數(shù)組中,
//默認數(shù)組中第一個值是已經(jīng)排好序的
void InsertSort(vector<int> &data)
{
    if(!data.empty())
        return;
    int size = data.size();
    for(int j = 1;j < size; ++j)//默認data[0]是排好序的
    {
        int temp = data[j];
        int index = j-1;
        while(index >= 0 && data[index] > temp)
        {
            data[index+1] = data[index];
            index--;
        }
        data[index+1] = temp;
    }
}
//歸并排序,先分治,在歸并
//假定sub1和sub2都是排好序的,result里面包含sub1和sub2中的所有元素
void Merge(vector<int> &result,vector<int> &sub1,vector<int> &sub2)
{
    sub1.push_back(INT_MAX);
    sub2.push_back(INT_MAX);
    int number1 = sub1.size();
    int number2 = sub2.size();
    int sub1_i = 0,sub2_i = 0;
    for(auto it = result.begin();it != result.end();++it)
    {
        if(sub1[sub1_i] <= sub2[sub2_i])
        {
            *it = sub1[sub1_i];
            ++sub1_i;
        }
        else
        {
            *it = sub2[sub2_i];
            ++sub2_i;
        }
    }
}
void MergeSort(vector<int>& coll)//合并排序,先分治法,再合并
{
    unsigned int number=coll.size();
    if(number<=1)
        return;
    unsigned int mid=number/2;
    vector<int> sub1;
    vector<int> sub2;
    for(unsigned int i=0;i<mid;++i)
    {
        sub1.push_back(coll[i]);
    }
    for(unsigned int j=0;j<number-mid;++j)
    {
        sub2.push_back(coll[mid+j]);
    }
    MergeSort(sub1);
    MergeSort(sub2);
    Merge(coll,sub1,sub2);
}
//冒泡排序法,每次總是拿當前循環(huán)的值與還沒排好序的值進行比較交換,把這一輪
//中最小的值放在當前循環(huán)的下標數(shù)組中,每循環(huán)一次,就排好一個較小的值,這樣循環(huán)n次,就排好序了
void BubleSort(vector<int> &data)
{
    int size = data.size();
    bool sort_flag = false;
    for(int i = 0;i < size;++i)
    {
        if(sort_flag == true) //冒泡改進版,當sort_flag = false;在某次循環(huán)中沒有執(zhí)行時,說明剩下的元素都排好序了
            return;
        sort_flag = true;
        for(int j = i;j < size;++j)//經(jīng)過一次循環(huán),將最小的值放在i處
        {
            if(data[i] > data[j])
            {
                swap(data[i],data[j]);
                sort_flag = false;
            }
        }
    }
}
//----------------------------------以下是不穩(wěn)定排序算法-------------------------
//快速排序
int Partition(int data[],int length,int start,int end)
{
    if(data == NULL || length <= 0 || start < 0 || end >= length)
        throw new exception(" Invalid Parameters");
    int index = rand()%(start-end+1)+start;
    swap(data[index],data[end]);
    int left = start-1;//小值放在左邊,大值放在右邊,循環(huán)時,if條件不成立時說明發(fā)現(xiàn)小值,否則一直值大值
    for(index = start;index < end;++index)
    {
        if(data[index] < data[end])
        {
            ++left;
            if(left != index)
            swap(data[left],data[index]);
        }
    }
    ++left;
    swap(data[left],data[end]);
    return left;
}
void QuickSort(int data[],int length,int start,int end)
{
    if(start == end)
        return;
    int index = Partition(data,length,start,end);
    if(index > start)
        QuickSort(data,length,start,index-1);
    if(index < end)
        QuickSort(data,length,index+1,end);
}
//堆排序 1.堆維護 2、建堆 3、堆排序
void MaxHeapIFY(vector<int> &data,int local,int length)//堆維護,local為要維護的元素的下標,length為數(shù)組的長度
{
    if(!data.empty())
        return;
    int left = local*2+1;//因為是從0開始計數(shù),所以計算公式有2i變?yōu)榇斯?br />     int right = local*2;
    int largest = local;
    if(left < length && data[left] > data[local])
    {
        largest = left;
    }
    if(right < length && data[right] > data[local])
    {
        largest = right;
    }
    if(largest != local)
    {
        swap(data[largest],data[local]);
        MaxHeapIFY(data,largest,length);//largest為退出遞歸的條件,當他大于length時,即終止遞歸
    }
}
//建堆,是從第一個非葉子節(jié)點(length/2-1)進行堆維護
void BuileMaxHeap(vector<int> &data ,int length)
{
    int root = length/2-1;
    for(int i = root;i >= 0;--i)
    {
        MaxHeapIFY(data,i,length);
    }
}
//將第一個元素的值和最后一個元素相互交換,然后舍去最后一個元素,用剩下的n-1個元素進行堆維護,逐個遞減到最后一個元素
void HeapSort(vector<int> &data)
{
    if(!data.empty())
        return;
    BuileMaxHeap(data,data.size());
    int length = data.size();
    for(int i = length-1;i >= 0;--i)
    {
        swap(data[0],data[i]);
        --length;
        MaxHeapIFY(data,0,length);     
    }
}
//選擇排序,每次選擇一個本循環(huán)中最小的值,與冒泡排序差不多,只不過少了交換的次數(shù),是直接進行排序的
void SelectionSort(vector<int> &data)
{
    int size = data.size();
    --size;
    for(int i = 0;i < size-1;++i)
    {
        int min = i;
        for(int j = i+1;j < size;++j)
        {
            if(data[min] > data[j])
                min = j;
        }
        swap(data[min],data[i]);
    }
}
//希爾排序,思想就是插入排序,把待排序的數(shù)組分成d組(下標每間隔為d的進行元素為一組),然后每組進行插入排序,
//接著遞減d的值,然后插入排序,直到d=1最后的排序,這樣比插入排序來說,減少了排序次數(shù),相當于跳著進行插入排序,最后跳度為1
void ShellSort(vector<int> &data)
{
    int size = data.size();
    size;
    int separate = size / 2;
    while(separate > 0)
    {
        for(int i = separate;i < size;++i)
        {
            int temp = data[i];
            int j = i - separate;
            while(j >=0 && data[j] > temp)
            {
                data[j+separate] = data[j];
                j = j-separate;
            }
            data[j+separate] = temp;
        }
        separate /= 2;//遞減增量
    }
}

總結: 每種算法都要它適用的條件,本文也僅僅是回顧了下基礎。有需要的可以參考。

相關文章

  • c++非變易算法-stl算法

    c++非變易算法-stl算法

    本文主要介紹了C++ STL算法庫中的非變易算法,是一些原則上不會變更操作數(shù)據(jù)的算法,包括:逐個查找算法、元素搜索算法、元素統(tǒng)計算法、序列匹配算法、子序列搜索算法、這些函數(shù)均包含于<algorithm>頭文件,本文給出的所有代碼在VS2010中編譯運行通過
    2014-03-03
  • C++概念重載、覆蓋、隱藏的使用說明

    C++概念重載、覆蓋、隱藏的使用說明

    本篇文章介紹了,在C++中概念重載、覆蓋、隱藏的使用分析說明。需要的朋友參考下
    2013-05-05
  • C++用new創(chuàng)建對象和不用new創(chuàng)建對象的區(qū)別解析

    C++用new創(chuàng)建對象和不用new創(chuàng)建對象的區(qū)別解析

    在C++用new創(chuàng)建對象和不用new創(chuàng)建對象是有區(qū)別的,不知你是否清楚的了解它們到底有什么樣的區(qū)別呢?下面小編就用示例來告訴大家吧,需要的朋友可以過來參考下
    2013-07-07
  • OpenCV實現(xiàn)物體的凸包檢測的示例代碼

    OpenCV實現(xiàn)物體的凸包檢測的示例代碼

    給定二維平面上的點集,凸包就是將最外層的點連接起來構成的凸邊形,它是包含點集中所有的點。本文將利用OpenCV實現(xiàn)物體的凸包檢測,感興趣的可以了解一下
    2022-08-08
  • C++中實現(xiàn)OpenCV圖像分割與分水嶺算法

    C++中實現(xiàn)OpenCV圖像分割與分水嶺算法

    分水嶺算法是一種常用的圖像區(qū)域分割法,本文主要介紹了OpenCV圖像分割與分水嶺算法,使用C++實現(xiàn),具有一定的參考價值,感興趣的可以了解一下
    2021-06-06
  • C語言字符串左旋的兩種實現(xiàn)方法

    C語言字符串左旋的兩種實現(xiàn)方法

    匯編語言中有一種移位指令叫做循環(huán)左移(ROL),下面這篇文章主要給大家介紹了關于C語言字符串左旋的兩種實現(xiàn)方法,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下
    2023-02-02
  • C語言簡單實現(xiàn)計算字符個數(shù)的方法

    C語言簡單實現(xiàn)計算字符個數(shù)的方法

    這篇文章主要介紹了C語言簡單實現(xiàn)計算字符個數(shù)的方法,涉及C語言針對字符串的簡單遍歷與判定技巧,具有一定參考借鑒價值,需要的朋友可以參考下
    2015-07-07
  • Vs?Code中C/C++配置launch.json和tasks.json文件詳細步驟

    Vs?Code中C/C++配置launch.json和tasks.json文件詳細步驟

    使用VSCode開發(fā)C/C++程序,需要配置tasks.json/launch.json,下面這篇文章主要給大家介紹了關于Vs?Code中C/C++配置launch.json和tasks.json文件的相關資料,文中通過圖文介紹的非常詳細,需要的朋友可以參考下
    2024-01-01
  • C++實現(xiàn)控制臺隨機迷宮的示例代碼

    C++實現(xiàn)控制臺隨機迷宮的示例代碼

    本文主要介紹了C++實現(xiàn)控制臺隨機迷宮的示例代碼,文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-08-08
  • C++實現(xiàn)班級成績管理系統(tǒng)

    C++實現(xiàn)班級成績管理系統(tǒng)

    這篇文章主要為大家詳細介紹了C++實現(xiàn)班級成績管理系統(tǒng),文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-02-02

最新評論