青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

匯流成河

碎片散落 星光點點

內部排序算法的比較和實現



排序是數據處理中經常使用的一種重要運算,在計算機及其應用系統中,花費在排序上的時間在系統運行時間中占有很大比重;并且排序本身對推動算法分析的發展 也起很大作用。目前已有上百種排序方法,但尚未有一個最理想的盡如人意的方法,本文介紹常用的如下排序方法的C/C++實現,并對它們進行分析和比較。
更詳細的算法思想的介紹可以參考這里 


/*
   冒泡排序  插入排序 二路插入排序 希爾排序   快速排序 選擇排序 歸并排序  堆排序算法的
   C/C++實現。
   
   作者:feosun

   日期:2008年10月12日

   參考資料:數據結構(C語言版) 清華大學出版社

*/


#include 
<iostream>
using namespace std;


//交換兩個數的值
void swap(int &a,int &b)
{
    
int tmp;
    tmp
=a;
    a
=b;
    b
=tmp;
}

//屏幕輸出數組
void display(int array[],int len)
{
    cout
<<"the result is:"<<endl;
    
for (int i = 0 ;i < len;i++ )
    {
        cout
<<array[i]<<"  ";
    }
    cout
<<endl;
}

/*
冒泡排序

算法思想:將被排序的記錄數組R[1..n]垂直排列,每個記錄R[i]看作是重量為R[i].key的氣泡。
          根據輕氣泡不能在重氣泡之下的原則,從下往上掃描數組 R:凡掃描到違反本原則的
          輕氣泡,就使其向上"飄浮"。如此反復進行,直到最后任何兩個氣泡都是輕者在上,
          重者在下為止。

時間復雜度 o(n^2)

空間復雜度 o(1)

比較次數 n(n+1)/2
*/
void bubble_sort(int array[],int len)
{
    
    
for (int i = len-1 ;i >= 0;i-- )
    {
        
for(int j = 0;j < i;j++)
            
if(array[j] > array[j+1])
                swap(array[j],array[j
+1]);
    }
}


/*
直接插入排序

算法思想:把n個待排序的元素看成為一個有序表和一個無序表,開始時有序表中只包含一個元
          素,無序表中包含有n-1個元素,排序過程中每次從無序表中取出第一個元素,將它
          插入到有序表中的適當位置,使之成為新的有序表,重復n-1次可完成排序過程。

時間復雜度 o(n^2)

空間復雜度 o(1)

比較次數 n(n+1)/2
*/
void insert_sort(int array[],int len)
{
    
int tmp,i,j;

    
for(i = 1;i < len;i++)
    {
        
if (array[i] < array[i-1])
        {
            tmp 
= array[i];
            array[i] 
= array[i-1];

            
//插入到相應位置
            for (j = i-2;j >= 0;j--)
            {
                
//往后移
                    if (array[j] > tmp )
                        array[j
+1= array[j];
                    
else
                    {
                        array[j
+1= tmp;
                        
break;
                    }
            }
            
if(j == -1)
            array[j
+1= tmp;
        }
    }
}


/*
2-路插入排序

算法思想:增加一個輔助空間d,把r[1]賦值給d[1],并將d[1]看成是排好序后處于中間
          位置的記錄。然后從r[2]開始依次插入到d[1]之前或之后的有序序列中。

時間復雜度 o(n^2)

空間復雜度 o(1)

比較次數 n(n+1)/2
*/

void bi_insert_sort(int array[],int len)
{
    
int* arr_d = (int *)malloc(sizeof(int* len);

    arr_d[
0= array[0];
    
int head = 0,tail = 0;
    
for (int i = 1;i < len; i++ )
    {
        
if (array[i] > arr_d[0])
        {
            
int j;
            
for ( j= tail;j>0;j--)
            {
                
if (array[i] < arr_d[j])
                    arr_d[j
+1= arr_d[j];
                
else
                    
break;
            }
            arr_d[j
+1= array[i];
            tail 
+= 1;
        }

        
else
        {
            
if (head ==0)
            {
                arr_d[len
-1= array[i];
                head 
=len-1;
            }
            
else
            {
                
int j;
                
for (j = head;j <= len-1;j++)
                {
                    
if (array[i] > arr_d[j])
                        arr_d[j
-1= arr_d[j];
                    
else
                        
break;
                }
                arr_d[j
-1= array[i];
                head 
-= 1;
            }
        }

    }

    
for (int i = 0;i < len; i++)
    {
        
int pos = (i + head );
        
if(pos >= len) pos -= len;
        array[i] 
= arr_d[pos];
    }

    free(arr_d);
}


/*
希爾排序

算法思想:先將整個待排序記錄分割成若干子序列分別進行直接插入排
          序,待整個序列中的記錄基本有序時,再對全體記錄進行一
          次直接插入排序

時間復雜度 o(n^2)

空間復雜度 o(1)

比較次數 ?
*/

void shell_insert(int array[],int d,int len)
{
    
int tmp,j;

    
for (int i = d;i < len;i++)
    {
        
if(array[i] < array[i-d])
        {
            tmp 
= array[i];
            j 
= i - d;
            
do 
            {
                array[j
+d] = array[j];
                j 
= j - d;
            } 
while (j >= 0 && tmp < array[j]);

            array[j
+d] = tmp; 
        }
    }
}
void shell_sort(int array[],int len)
{

    
int inc = len;

    
do 
    {
        inc 
= inc/2;
        shell_insert(array,inc,len);
    } 
while (inc > 1);
}




/*
快速排序

算法思想:將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞
          歸地解這些子問題,然后將這些子問題的解組合成為原問題的解。

時間復雜度 o(nlogn)

空間復雜度 o(logn)

比較次數  ?
*/

int partition(int array[],int low,int high)
{
    
int  pivotkey = array[low];

    
while (low < high)
    {
        
while(low < high && array[high] >= pivotkey)
            
--high;
        swap(array[low],array[high]);

        
while(low < high && array[low] <= pivotkey)
            
++low;
        swap(array[low],array[high]);
    }

    array[low] 
= pivotkey;

    
return low;
}


void quick_sort(int array[],int low,int high)
{
    
if (low < high)
    {
        
int pivotloc = partition(array,low,high);
        quick_sort(array,low,pivotloc
-1);
        quick_sort(array,pivotloc
+1,high);
    }
}



/*
直接選擇排序

算法思想:每一趟在n-i+1個記錄中選取關鍵字最小的記錄作為有序序列中的第i個記錄

時間復雜度 o(n^2)

空間復雜度 o(1) ?

比較次數  n(n+1)/2
*/

int SelectMinKey(int array[],int iPos,int len)
{
    
int ret = 0;

    
for (int i = iPos; i < len; i++)
    {
        
if (array[ret] > array[i])
        {
            ret 
= i;
        }
    }
    
return ret;
}

void select_sort(int array[],int len)
{
    
for (int i = 0; i < len; i++)
    {
        
int j = SelectMinKey(array,i,len);
        
if (i != j)
        {
            swap(array[i],array[j]);
        }
    }
}





/*
歸并排序

算法思想:設兩個有序的子文件(相當于輸入堆)放在同一向量中相鄰的位置上:R[low..m],R[m+1..high],先
          將它們合并到一個局部的暫存向量R1(相當于輸出堆)中,待合并完成后將R1復制回R[low..high]中。

時間復雜度 o(nlogn)

空間復雜度 o(n) 

比較次數  ?
*/

void merge(int array[],int i,int m, int n)
{
    
int j,k;

    
int iStart = i, iEnd = n;

    
int arrayDest[256];

    
for ( j = m + 1,k = i; i <= m && j <= n; ++k)
    {
        
if (array[i] < array[j])
            arrayDest[k] 
= array[i++];
        
else
            arrayDest[k] 
= array[j++];
    }

    
if (i <= m)
        
for (;k <= n; k++,i++)
            arrayDest[k] 
= array[i];
    
if(j <= n)
        
for (;k <= n; k++,j++)
            arrayDest[k] 
= array[j];

    
for(j = iStart; j <= iEnd; j++)
        array[j] 
= arrayDest[j];
}



void merge_sort(int array[],int s,int t)
{
    
int m;

    
if (s < t) 
    {
        m 
= (s + t )/2;
        merge_sort(array,s,m);
        merge_sort(array,m
+1,t);
        merge(array,s,m,t);

    }
}


/*
堆排序

算法思想:堆排序(Heap Sort)是指利用堆(heaps)這種數據結構來構造的一種排序算法。
          堆是一個近似完全二叉樹結構,并同時滿足堆屬性:即子節點的鍵值或索引總是
          小于(或者大于)它的父節點。

時間復雜度 o(nlogn)

空間復雜度 o(1) 

比較次數  較多
*/

void heap_adjust(int array[],int i,int len)
{
    
int rc = array[i];

    
for(int j = 2 * i; j <len; j *= 2)
    {
        
if(j < len && array[j] < array[j+1]) j++;
        
if(rc >= array[j]) break;

        array[i] 
= array[j]; i = j;
    }
    array[i] 
= rc;
}





void heap_sort(int array[],int len)
{
    
int i;
    
for(i = (len-1)/2; i >= 0; i--)
        heap_adjust(array,i,len);
    
for(  i = (len-1); i > 0; i--)
    {
        swap(array[
0],array[i]);   //彈出最大值,重新對i-1個元素建堆
        heap_adjust(array,0,i-1);
    }

}








int main() {

    
int array[] = {45,56,76,234,1,34,23,2,3,55,88,100};

    
int len = sizeof(array)/sizeof(int);



    
//bubble_sort(array,len);           //冒泡排序

    
/*insert_sort(array,len);*/         //插入排序

    
/*bi_insert_sort(array,len);*/      //二路插入排序
    
    
/*shell_sort(array,len);*/          //希爾排序 

    
/*quick_sort(array,0,len-1);*/      //快速排序
    
    
/*select_sort(array,len);*/         //選擇排序

    
/*merge_sort(array,0,len-1);*/      //歸并排序
    
    heap_sort(array,len);               
//堆排序
    display(array,len);



    
return 0;
}




選擇排序、快速排序、希爾排序、堆排序不是穩定的排序算法,而冒泡排序、插入排序、歸并排序和基數排序是穩定的排序算法。


      首先,排序算法的穩定性大家應該都知道,通俗地講就是能保證排序前2個相等的數其在序列的前后位置順序和排序后它們兩個的前后位置順序相同。在簡單形式化一下,如果Ai = Aj, Ai原來在位置前,排序后Ai還是要在Aj位置前。

     其次,說一下穩定性的好處。排序算法如果是穩定的,那么從一個鍵上排序,然后再從另一個鍵上排序,第一個鍵排序的結果可以為第二個鍵排序所用?;鶖蹬判蚓? 是這樣,先按低位排序,逐次按高位排序,低位相同的元素其順序再高位也相同時是不會改變的。另外,如果排序算法穩定,對基于比較的排序算法而言,元素交換 的次數可能會少一些(個人感覺,沒有證實)。

     回到主題,現在分析一下常見的排序算法的穩定性,每個都給出簡單的理由。

   (1)冒泡排序

        冒泡排序就是把小的元素往前調或者把大的元素往后調。比較是相鄰的兩個元素比較,交換也發生在這兩個元素之間。所以,如果兩個元素相等,我想你是不會再無 聊地把他們倆交換一下的;如果兩個相等的元素沒有相鄰,那么即使通過前面的兩兩交換把兩個相鄰起來,這時候也不會交換,所以相同元素的前后順序并沒有改 變,所以冒泡排序是一種穩定排序算法。

(2)選擇排序

      選擇排序是給每個位置選擇當前元素最小的,比如給第一個位置選擇最小的,在剩余元素里面給第二個元素選擇第二小的,依次類推,直到第n-1個元素,第n個 元素不用選擇了,因為只剩下它一個最大的元素了。那么,在一趟選擇,如果當前元素比一個元素小,而該小的元素又出現在一個和當前元素相等的元素后面,那么 交換后穩定性就被破壞了。比較拗口,舉個例子,序列5 8 5 2 9,我們知道第一遍選擇第1個元素5會和2交換,那么原序列中2個5的相對前后順序就被破壞了,所以選擇排序不是一個穩定的排序算法。

(3)插入排序
     插入排序是在一個已經有序的小序列的基礎上,一次插入一個元素。當然,剛開始這個有序的小序列只有1個元素,就是第一個元素。比較是從有序序列的末尾開 始,也就是想要插入的元素和已經有序的最大者開始比起,如果比它大則直接插入在其后面,否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相 等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后順序沒有改變,從原無序序列出去的順序就是排好序后的順序,所以插入排序是穩 定的。

(4)快速排序
    快速排序有兩個方向,左邊的i下標一直往右走,當a[i] <= a[center_index],其中center_index是中樞元素的數組下標,一般取為數組第0個元素。而右邊的j下標一直往左走,當a[j] > a[center_index]。如果i和j都走不動了,i <= j, 交換a[i]和a[j],重復上面的過程,直到i>j。交換a[j]和a[center_index],完成一趟快速排序。在中樞元素和a[j]交 換的時候,很有可能把前面的元素的穩定性打亂,比如序列為 5 3 3 4 3 8 9 10 11,現在中樞元素5和3(第5個元素,下標從1開始計)交換就會把元素3的穩定性打亂,所以快速排序是一個不穩定的排序算法,不穩定發生在中樞元素和 a[j] 交換的時刻。

(5)歸并排序
    歸并排序是把序列遞歸地分成短序列,遞歸出口是短序列只有1個元素(認為直接有序)或者2個序列(1次比較和交換),然后把各個有序的段序列合并成一個有 序的長序列,不斷合并直到原序列全部排好序。可以發現,在1個或2個元素時,1個元素不會交換,2個元素如果大小相等也沒有人故意交換,這不會破壞穩定 性。那么,在短的有序序列合并的過程中,穩定是是否受到破壞?沒有,合并過程中我們可以保證如果兩個當前元素相等時,我們把處在前面的序列的元素保存在結 果序列的前面,這樣就保證了穩定性。所以,歸并排序也是穩定的排序算法。

(6)基數排序
   基數排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次類推,直到最高位。有時候有些屬性是有優先級順序的,先按低優先級排序,再按高優 先級排序,最后的次序就是高優先級高的在前,高優先級相同的低優先級高的在前?;鶖蹬判蚧诜謩e排序,分別收集,所以其是穩定的排序算法。

(7)希爾排序(shell)
    希爾排序是按照不同步長對元素進行插入排序,當剛開始元素很無序的時候,步長最大,所以插入排序的元素個數很少,速度很快;當元素基本有序了,步長很小, 插入排序對于有序的序列效率很高。所以,希爾排序的時間復雜度會比o(n^2)好一些。由于多次插入排序,我們知道一次插入排序是穩定的,不會改變相同元 素的相對順序,但在不同的插入排序過程中,相同的元素可能在各自的插入排序中移動,最后其穩定性就會被打亂,所以shell排序是不穩定的。

(8)堆排序
   我們知道堆的結構是節點i的孩子為2*i和2*i+1節點,大頂堆要求父節點大于等于其2個子節點,小頂堆要求父節點小于等于其2個子節點。在一個長為n 的序列,堆排序的過程是從第n/2開始和其子節點共3個值選擇最大(大頂堆)或者最小(小頂堆),這3個元素之間的選擇當然不會破壞穩定性。但當為n /2-1, n/2-2, ...1這些個父節點選擇元素時,就會破壞穩定性。有可能第n/2個父節點交換把后面一個元素交換過去了,而第n/2-1個父節點把后面一個相同的元素沒 有交換,那么這2個相同的元素之間的穩定性就被破壞了。所以,堆排序不是穩定的排序算法。

posted on 2008-10-12 20:56 feosun 閱讀(4762) 評論(2)  編輯 收藏 引用 所屬分類: Algorithm

Feedback

# re: 內部排序算法的C/C++實現 2008-10-13 09:12 Fox

呵呵,整理的不錯:)  回復  更多評論   

# re: 內部排序算法的比較和實現[未登錄] 2013-07-02 11:12 glory

很強大,都編程實現了,但是在直接選擇排序中,有一處錯誤,
int SelectMinKey(int array[],int iPos,int len)
中 int ret = 0;應該是ret=iPos,否則每次就不是從ipos~len中選擇最小的了@Fox  回復  更多評論   


青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            久久深夜福利| 久久精品欧洲| 亚洲三级免费电影| 久久久综合免费视频| 国产欧美一区二区精品婷婷| 午夜日韩在线| 欧美一区二区三区久久精品| 国产视频精品网| 欧美精品日韩一本| 欧美日韩另类字幕中文| 亚洲视频在线一区| 亚洲免费视频中文字幕| 国产日本欧洲亚洲| 欧美成人在线免费观看| 欧美日韩国产色站一区二区三区| 在线视频精品一区| 午夜欧美精品| 亚洲理论在线观看| 亚洲欧美日韩成人高清在线一区| 黑人一区二区三区四区五区| 亚洲第一天堂av| 国产精品爱久久久久久久| 久久国产主播| 欧美另类99xxxxx| 久久精品午夜| 欧美激情中文字幕一区二区| 亚洲欧美中文日韩v在线观看| 欧美中文字幕在线播放| 亚洲美女av黄| 欧美在线免费| 中国av一区| 久久在线视频在线| 先锋影音久久| 欧美日韩国产首页| 欧美成人dvd在线视频| 国产精品国产三级国产专播品爱网| 久久免费黄色| 国产精品一区二区a| 亚洲黄一区二区三区| 国产有码一区二区| 亚洲影院色无极综合| 亚洲精品久久久一区二区三区| 亚洲午夜性刺激影院| 最近中文字幕mv在线一区二区三区四区| 一区二区三区四区蜜桃| 91久久在线播放| 久久亚洲精品伦理| 久久国产精品99国产精| 欧美日韩在线亚洲一区蜜芽| 欧美搞黄网站| 亚洲第一中文字幕| 久久99在线观看| 久久激情婷婷| 国产视频一区在线观看一区免费| 99xxxx成人网| 亚洲午夜在线观看| 欧美日韩高清不卡| 最近看过的日韩成人| 亚洲黄色在线| 六十路精品视频| 久久综合久久综合这里只有精品| 国产精品一区二区久久久久| 亚洲视频综合在线| 香蕉成人久久| 国产区欧美区日韩区| 亚洲欧美变态国产另类| 午夜免费电影一区在线观看| 欧美日韩在线观看一区二区| 亚洲精品午夜| 亚洲自拍偷拍一区| 国产精品美女一区二区在线观看 | 久久久亚洲人| 美女视频黄 久久| 欧美激情精品久久久久| 亚洲在线播放| 国产美女精品免费电影| 欧美一级视频一区二区| 久久久久久亚洲精品杨幂换脸| 国产日韩欧美综合| 欧美伊久线香蕉线新在线| 久久久久久久久久久一区| 在线观看欧美日韩国产| 欧美成人午夜激情视频| 亚洲美女中文字幕| 亚洲欧美www| 韩国av一区二区| 欧美sm视频| 亚洲视频每日更新| 久久久噜噜噜久久中文字幕色伊伊| 尤物视频一区二区| 欧美日本网站| 久久动漫亚洲| 亚洲啪啪91| 欧美影院视频| 亚洲日韩成人| 国产精品久久久久秋霞鲁丝 | 久久尤物视频| 夜夜嗨av一区二区三区四季av| 国产精品xxxav免费视频| 久久精品国产精品亚洲综合| 亚洲高清av在线| 午夜视频精品| 最新中文字幕一区二区三区| 欧美四级在线观看| 久久久人人人| 国产精品99久久久久久宅男 | 一区二区三区四区精品| 国产亚洲一区二区在线观看 | 国产日韩欧美在线观看| 免费亚洲电影在线观看| 亚洲一本视频| 亚洲二区视频| 久久视频在线免费观看| 亚洲一品av免费观看| 在线观看精品| 国产视频精品网| 欧美三级午夜理伦三级中视频| 久久精品一级爱片| 亚洲免费网址| 国产综合久久久久久鬼色| 亚洲一区二区三区成人在线视频精品| 国产精品每日更新| 欧美老女人xx| 久久视频在线看| 久久精品视频在线播放| 亚洲视频网在线直播| 亚洲片区在线| 亚洲第一在线视频| 久久美女性网| 久久成人av少妇免费| 午夜精品美女久久久久av福利| 亚洲精品国产精品乱码不99按摩| 国内免费精品永久在线视频| 国产精品美女久久久久久久 | 久久国内精品视频| 欧美一区二区高清在线观看| 亚洲小视频在线观看| 这里是久久伊人| 国产日韩视频| 欧美日韩综合网| 欧美乱妇高清无乱码| 免费日韩成人| 欧美黄色一区二区| 欧美日韩亚洲91| 欧美日韩爆操| 欧美区在线播放| 欧美日韩国产一区精品一区| 欧美另类极品videosbest最新版本| 免费看成人av| 欧美精品啪啪| 欧美视频网址| 国产精品婷婷午夜在线观看| 国产精品亚洲欧美| 国产午夜精品美女视频明星a级 | 亚洲午夜在线观看视频在线| 在线一区二区视频| 亚洲欧美日韩国产成人精品影院 | 亚洲高清视频在线观看| 亚洲精品国偷自产在线99热| 日韩一级黄色av| 午夜精品久久久久久久蜜桃app| 午夜精品久久久久久久99水蜜桃 | 激情综合色丁香一区二区| 亚洲大胆在线| 亚洲免费观看高清完整版在线观看熊 | 欧美四级伦理在线| 国产一区二区看久久| 亚洲丶国产丶欧美一区二区三区| 亚洲人成绝费网站色www| 国产精品99久久99久久久二8| 亚洲欧美久久久| 免费成人性网站| 一本色道精品久久一区二区三区| 亚洲在线成人| 欧美96在线丨欧| 国产精品试看| 亚洲国产精品久久久久| 亚洲一区三区视频在线观看| 久久本道综合色狠狠五月| 欧美激情91| 午夜精品久久久久久久99黑人| 蜜桃av一区二区三区| 国产精品视频网址| 亚洲经典三级| 久久久久9999亚洲精品| 亚洲人精品午夜| 欧美影院精品一区| 欧美日韩在线另类| 一区视频在线播放| 亚洲欧美日韩在线播放| 欧美成人在线免费视频| 亚洲一区三区电影在线观看| 裸体丰满少妇做受久久99精品| 国产精品电影在线观看| 亚洲人成免费| 免费成人高清| 欧美在线视频在线播放完整版免费观看| 欧美韩日高清| 亚洲高清免费| 久久综合狠狠综合久久综合88|