C語言奇偶排序算法詳解及實例代碼
歸併排序(Merge sort)是創建在歸併操作上的一種有效的排序算法。該算法是採用分治法的一個非常典型的應用。本文特意為大家收集整理了C語言奇偶排序算法詳解及實例代碼,希望大家喜歡!
一個歸併排序的.例子:對一個隨機點的鏈表進行排序
算法描述
歸併操作的過程如下:
申請空間,使其大小為兩個已經排序序列之和,該空間用來存放合併後的序列 設定兩個指針,最初位置分別為兩個已經排序序列的起始位置 比較兩個指針所指向的元素,選擇相對小的元素放入到合併空間,並移動指針到下一位置 重複步驟3直到某一指針到達序列尾 將另一序列剩下的所有元素直接複製到合併序列尾
特點:歸併排序是穩定的排序.即相等的元素的順序不會改變, 速度僅次於快速排序,但較穩定。
歸併操作
歸併操作(merge),也叫歸併算法,指的是將兩個順序序列合併成一個順序序列的方法。
如:設有數列 [6,202,100,301,38,8,1]
初始狀態:6, 202, 100, 301, 38, 8, 1
第一次歸併後:[6, 202], [100, 301], [8, 38], [1],比較次數:3;
第二次歸併後:[6, 100, 202, 301],[1, 8, 38],比較次數:4;
第三次歸併後:[1, 6, 8, 38, 100, 202, 301],比較次數:4;
總的比較次數為:3+4+4=11,;
逆序數為14;
算法實現
// Completed on 2014.10.11 17:20
// Language: C99
//
// 版權所有(C)codingwu (mail: )
// 博客地址:
#include
#includevoid merge_sort(int *list, const int first, const int last)
{
int len= last-first+1;
int left_min,left_max; //左半區域邊界
int right_min,right_max; //右半區域邊界
int index;
int i;
int *tmp;
tmp = (int *)malloc(sizeof(int)*len);
if( tmp == NULL || len <= 0 )
return;
for( i = 1; i < len; i *= 2 )
{
for( left_min = 0; left_min < len - i; left_min = right_max)
{
int j;
right_min = left_max = left_min + i;
right_max = left_max + i;
j = left_min;
if ( right_max > len )
right_max = len;
index = 0;
while( left_min < left_max && right_min < right_max )
{
tmp[index++] = (list[left_min] > list[right_min] ? list[right_min++] : list[left_min++]);
}
while( left_min < left_max )
{
list[--right_min] = list[--left_max];
}
while( index > 0 )
{
list[--right_min] = tmp[--index];
}
}
}
free(tmp);
}
int main()
{
int a[] = {288, 52, 123, 30, 212, 23, 10, 233};
int n, mid;
n = sizeof(a) / sizeof(a[0]);
mid = n / 2;
merge_sort(a, 0, n - 1);
for(int k = 0; k < n; k++)
printf("%d ", a[k]);
printf("n");
return 0;
}
使用遞歸實現:
// Completed on 2014.10.11 18:20
// Language: C99
//
// 版權所有(C)codingwu (mail: )
// 博客地址:
#include
#include
void merge(int *array,const int first, const int mid, const int last)
{
int i,index;
int first1,last1;
int first2,last2;
int *tmp;
tmp = (int *)malloc((last-first+1)*sizeof(int));
if( tmp == NULL )
return;
first1 = first;
last1 = mid;
first2 = mid+1;
last2 = last;
index = 0;
while( (first1 <= last1) && (first2 <= last2) )
{
if( array[first1] < array[first2] )
{
tmp[index++] = array[first1];
first1++;
}
else{
tmp[index++] = array[first2];
first2++;
}
}
while( first1 <= last1 )
{
tmp[index++] = array[first1++];
}
while( first2 <= last2 )
{
tmp[index++] = array[first2++];
}
for( i=0; i<(last-first+1); i++)
{
array[first+i] = tmp[i];
}
free(tmp);
}
void merge_sort(int *array, const int first, const int last)
{
int mid = 0;
if(first < last)
{
mid = (first + last) / 2;
merge_sort(array, first, mid);
merge_sort(array, mid + 1, last);
merge(array, first, mid, last);
}
}
int main()
{
int a[] = {288, 52, 123, 30, 212, 23, 10, 233};
int n, mid;
n = sizeof(a) / sizeof(a[0]);
mid = n / 2;
merge_sort(a, 0, n - 1);
for(int k = 0; k < n; k++)
printf("%d ", a[k]);
printf("n");
return 0;
}
-
為什麼入門首選C語言?
C語言的設計目標是提供一種能以簡易的方式編譯、處理低級存儲器、產生少量的機器碼以及不需要任何運行環境支持便能運行的編程語言。對於大部分程序員,C語言是學習編程的第一門語言,很少有不瞭解C的程序員。那麼為什麼入門首選C語言呢,下面小編為大家介紹一下吧!C...
-
C語言中gets()函數知識
導語:gets從標準輸入設備讀字符串函數,其可以無限讀取,不會判斷上限,以回車結束讀取,所以程序員應該確保buffer的空間足夠大,以便在執行讀操作時不發生溢出。。下面是C語言中gets()函數知識,一起來學習下吧:gets()函數用於從緩衝區中讀取字符串,其原型如下:char*gets(cha...
-
2017計算機二級C語言上機考試技巧
引導語:在計算機二級C語言考題中要求考生把一道C語言程序考題,通過考生自己編寫的函數補充完整,共同完成考題的一項或多項任務。以下是本站小編分享給大家的2017計算機二級C語言上機考試技巧,歡迎閲讀!第一部:備考篇名將不打無準備之仗,複習備考的好壞,是能否順利通過...
-
C語言與JAVA的區別
很多人不明白C語言與C++和JAVE之間的區別,為此,為大家收集整理了下面的內容,歡迎閲讀!C語言C語言是一門通用計算機編程語言,應用廣泛。C語言的設計目標是提供一種能以簡易的方式編譯、處理低級存儲器、產生少量的機器碼以及不需要任何運行環境支持便能運行的編程語...