c語言用比較排序法,C語言比較排序

本文目錄一覽：

• 1、計算機C語言中關於比較排序的問題
• 2、c語言排序的方法
• 3、c語言做各種排序演算法比較程序怎麼做？
• 4、豆丁c語言中幾種排序方法比較
• 5、c語言 比較法排序區別

計算機C語言中關於比較排序的問題

一、冒泡排序

已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與a[2]的值，若a[1]大於a[2]則交換兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大於a[3]則交換兩者的值，否則不變。再比較a[3]與a[4]，以此類推，最後比較a[n-1]與a[n]的值。這樣處理一輪後，a[n]的值一定是這組數據中最大的。再對a[1]~a[n-1]以相同方法處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理n-1輪後a[1]、a[2]、……a[n]就以升序排列了。

優點：穩定；

缺點：慢，每次只能移動相鄰兩個數據。

二、選擇排序

冒泡排序的改進版。

每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。

選擇排序是不穩定的排序方法。

n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：

①初始狀態：無序區為R[1..n]，有序區為空。

②第1趟排序

在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。

……

③第i趟排序

第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(1≤i≤n-1)。該趟排序從當前無序區中選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。

這樣，n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。

優點：移動數據的次數已知（n-1次）；

缺點：比較次數多。

三、插入排序

已知一組升序排列數據a[1]、a[2]、……a[n]，一組無序數據b[1]、b[2]、……b[m]，需將二者合併成一個升序數列。首先比較b[1]與a[1]的值，若b[1]大於a[1]，則跳過，比較b[1]與a[2]的值，若b[1]仍然大於a[2]，則繼續跳過，直到b[1]小於a數組中某一數據a[x]，則將a[x]~a[n]分別向後移動一位，將b[1]插入到原來a[x]的位置這就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若無數組a，可將b[1]當作n=1的數組a）

優點：穩定，快；

缺點：比較次數不一定，比較次數越少，插入點後的數據移動越多，特別是當數據總量龐大的時候，但用鏈表可以解決這個問題。

三、縮小增量排序

由希爾在1959年提出，又稱希爾排序(shell排序)。

已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。發現當n不大時，插入排序的效果很好。首先取一增量d(dn)，將a[1]、a[1+d]、a[1+2d]……列為第一組，a[2]、a[2+d]、a[2+2d]……列為第二組……，a[d]、a[2d]、a[3d]……列為最後一組以次類推，在各組內用插入排序，然後取d’d，重複上述操作，直到d=1。

優點：快，數據移動少；

缺點：不穩定，d的取值是多少，應取多少個不同的值，都無法確切知道，只能憑經驗來取。

四、快速排序

快速排序是目前已知的最快的排序方法。

已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先任取數據a[x]作為基準。比較a[x]與其它數據並排序，使a[x]排在數據的第k位，並且使a[1]~a[k-1]中的每一個數據a[x]，a[k+1]~a[n]中的每一個數據a[x]，然後採用分治的策略分別對a[1]~a[k-1]和a[k+1]~a[n]兩組數據進行快速排序。

優點：極快，數據移動少；

缺點：不穩定。

五、箱排序

已知一組無序正整數數據a[1]、a[2]、……a[n]，需將其按升序排列。首先定義一個數組x[m],且m=a[1]、a[2]、……a[n]，接著循環n次，每次x[a]++.

優點：快，效率達到O(1)

缺點：數據範圍必須為正整數並且比較小

六、歸併排序

歸併排序是多次將兩個或兩個以上的有序表合併成一個新的有序表。最簡單的歸併是直接將兩個有序的子表合併成一個有序的表。

歸併排序是穩定的排序.即相等的元素的順序不會改變.如輸入記錄 1(1) 3(2) 2(3) 2(4) 5(5) (括弧中是記錄的關鍵字)時輸出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按輸入的順序.這對要排序數據包含多個信息而要按其中的某一個信息排序,要求其它信息盡量按輸入的順序排列時很重要.這也是它比快速排序優勢的地方.

c語言排序的方法

排序主要分為以下幾種。

1.冒泡排序:通過循環比較前後數的大小進行交換。最後使得數組有序。

2.快速排序:首先將第一個數作為一個基準，然後循環，將前半部分大於該數的與後半部分小於該數的進行交換，使得以該數為分界線，前面的小於該數，後面的大於該數，然後分前後兩部分繼續。

c語言做各種排序演算法比較程序怎麼做？

按照程序設計的自頂向下，逐步求精的機構化程序設計思想來完成這個任務。

①大概的頂層框架是：隨機數產生模塊，文件保存模塊，排序以及統計排序過程信息的模塊。

②分別設計出隨機數產生演算法，三種排序演算法。

③按照邏輯的順序進行組裝，並給出必要的過程信息。

演算法的設計實現以及程序運行結果：

豆丁c語言中幾種排序方法比較

1.穩定性比較

插入排序、冒泡排序、二叉樹排序、二路歸併排序及其他線性排序是穩定的

選擇排序、希爾排序、快速排序、堆排序是不穩定的

2.時間複雜性比較

插入排序、冒泡排序、選擇排序的時間複雜性為O(n2)

其它非線形排序的時間複雜性為O(nlog2n)

線形排序的時間複雜性為O(n);

3.輔助空間的比較

線形排序、二路歸併排序的輔助空間為O(n),其它排序的輔助空間為O(1);

4.其它比較

插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達到較快的速度。反而在這種情況下，快速排序反而慢了。

當n較小時，對穩定性不作要求時宜用選擇排序，對穩定性有要求時宜用插入或冒泡排序。

若待排序的記錄的關鍵字在一個明顯有限範圍內時,且空間允許是用桶排序。

當n較大時，關鍵字元素比較隨機，對穩定性沒要求宜用快速排序。

當n較大時，關鍵字元素可能出現本身是有序的，對穩定性有要求時，空間允許的情況下。宜用歸併排序。

當n較大時，關鍵字元素可能出現本身是有序的，對穩定性沒有要求時宜用堆排序。

c語言 比較法排序區別

1、穩定排序和非穩定排序的不同

簡單地說就是所有相等的數經過某種排序方法後，仍能保持它們在排序之前的相對次序，我們就說這種排序方法是穩定的。反之，就是非穩定的。

比如：一組數排序前是a1,a2,a3,a4,a5，其中a2=a4，經過某種排序後為a1,a2,a4,a3,a5，則我們說這種排序是穩定的，因為a2排序前在a4的前面，排序後它還是在a4的前面。假如變成a1,a4,a2,a3,a5就不是穩定的了。

2、內排序和外排序的不同

在排序過程中，所有需要排序的數都在內存，並在內存中調整它們的存儲順序，稱為內排序；

在排序過程中，只有部分數被調入內存，並藉助內存調整數在外存中的存放順序排序方法稱為外排序。

3、演算法的時間複雜度和空間複雜度不同

所謂演算法的時間複雜度，是指執行演算法所需要的計算工作量。

一個演算法的空間複雜度，一般是指執行這個演算法所需要的內存空間。