生活随笔
收集整理的這篇文章主要介紹了
C语言排序算法总结
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
From: http://www.diybl.com/course/6_system/linux/Linuxjs/20091028/180420.html
排序算法一直都是讓我頭疼的算法。為了全面掌握排序算法，我就整理了常用的排序算法。
首先我們來了解一些基本概念：
（1）穩定排序和非穩定排序
簡單地說就是所有相等的數經過某種排序方法后，仍能保持它們在排序之前的相對次序，我們就
說這種排序方法是穩定的。反之，就是非穩定的。
?比如：一組數排序前是a1,a2,a3,a4,a5，其中a2=a4，經過某種排序后為a1,a2,a4,a3,a5，
則我們說這種排序是穩定的，因為a2排序前在a4的前面，排序后它還是在a4的前面。假如變成a1,a4,
a2,a3,a5就不是穩定的了。
（2）內部排序和外部排序
在排序過程中，所有需要排序的數都在內存，并在內存中調整它們的存儲順序，稱為內排序；
在排序過程中，只有部分數被調入內存，并借助內存調整數在外存中的存放順序排序方法稱為外排序。
（3）算法的時間復雜度和空間復雜度
?所謂算法的時間復雜度，是指執行算法所需要的計算工作量。
?一個算法的空間復雜度，一般是指執行這個算法所需要的內存空間。
(1)選擇排序算法：它是非穩定的。每一趟在n-i+1個記錄中選取最小的記錄作為有序序列的第i的記錄。它的算法如下：
| void choose_sort(int *x, int n)/*x數組名 n為數組長度*/
{
????int i, j, min, k;
????for(i = 0; i < n-1; i++){
????????min = i;
????????for(j = i+1; j < n; j++){
????????????if(x[min] > x[j])
????????????????min = j;
????????}
????????if(min != i){
????????????k = x[i];
????????????x[i] = x[min];
????????????x[min] = k;
????????}
????}
} |
（2）直接插入排序：將一個記錄插入到排好序的記錄中，從而得到一個新的有序表。它的算法如下：
| void insert_sort(int *x, int n)
{
????int i, j, t;
????for(i = 1; i < n; i++){
????????t = x[i];
????????for(j = i-1; (j>=0&&t<x[j]); j--){
????????????x[j+1] = x[j];
????????}
????????x[j+1] = t;
????}
????
} |
（3）快速排序：是對冒泡排序的一種改進。它首先需要一個函數Partition()將要排序的記錄以low為中心分成兩個部分：比x[low]下小的放low前面，比x[low]大的放low后面。假設第一趟分成了如下兩部分：
x[s],x[s+1]...x[i-1]和x[i+1],x[i+1]...x[t]
可以看書，low==i.
之后我們這兩部分再進行Partition()函數排序。
Partition(int *x, int low, int high)解析：
我們從high開始逆序找，從low開始順序找，最后low等于high后便退出這一趟排序。代碼如下：
| int Partition(int *x, int low, int high)
{
????int key;
????key = x[low];
????while(low < high){
????????while((low < high) && x[high] >= key)
????????????high--;
??????? x[low] = x[high];
????????while((low < high) && x[low] <= key)
????????????low++;
??????? x[high] = x[low];
????}
????x[low] = key;
????return low;
} |
遞歸對所有被分割的序列排序：
| void QSort(int *x, int low, int high)
{
????int key_i;
????if(low < high){
????????key_i = Partition(x, low, high);
????????QSort(x, low, (key_i-1));
????????QSort(x, (key_i+1), high);
????}
} |
最后完成該函數：
void QuickSort(int *x, int n)
{
????QSort(x, 0, (n-1));
}
總結
以上是生活随笔為你收集整理的C语言排序算法总结的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
