一、快速排序
快速排序主要思想是“分治”，即把一個大問題分成若干小問題來分別解決。首先，從待排序的數據中選出一個“代表元”，然後把比代表元小的元素放在數組左邊，大的放在數組右邊。然後分別考慮左右兩部分，對其做相同處理，即從左右兩邊再分別選取代表元，再分。所以快速排序的一個主要步驟就是根據代表元進行數組重排列的過程，暫且稱其為partition()。快速排序代碼如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int partition( int head, int tail, int array[] )
{
int rep = array[tail];
int tail2 = tail;
while ( head < tail )
{
while( array[head] <= rep && head < tail )
{
head++;
}
while ( array[tail] >= rep && head < tail )
{
tail--;
}
if ( head < tail )
{
int tmp = array[tail];
array[tail] = array[head];
array[head] = tmp;
head++;
tail--;
}
}
array[tail2] = array[head];
array[head] = rep;
return head;
}
void quicksort( int head, int tail, int array[] )
{
int i;
if ( tail <= head )
{
for ( i = 0; i < 6; i++ )
printf( "%d", array[i] );
printf( "\n" );
return;
}
else
{
int q = partition( head, tail, array );
//printf( "%d\n", q );
quicksort( head, q - 1, array );
quicksort( q + 1, tail, array );
}
}
int main()
{
int array[6] = {1,2,3,5,4,2};
//int a = partition( 0, 1, array );
quicksort( 0, 5, array );
int i;
for ( i = 0; i < 6; i++ )
printf( "%d ", array[i] );
//printf( "%d", a );
return 0;
}然後考慮其復雜度，如果代表元選擇得當，使得每次數組劃分都能對半開，那麼復雜度就是T(n)=2*T(n)+n，即為O(n*logn)，但考慮最壞的情況，如果每次代表元的選擇都使得數組嚴重“偏沉”，那麼復雜度就是T(n)=T(n-1)+n，最後的復雜度就是O(n^2)。所以，快排雖好，但是不夠穩定。另外，快排需要O(logn)的額外空間，用於遞歸操作時代表元的存儲。
二、堆排序
堆其實就是一棵完全二叉樹，最大堆的定義就是說父節點大於兩個子節點，最小堆類似。堆排序算法利用了最大堆的一個性質：堆中父節點肯定是最大的。排序算法有兩個子函數：maxheapify()和buildmaxheap()，maxheapify()的功能是將一個節點和兩個已經是最大堆的子樹合並為一個最大堆，而buildmaxheap()的功能是將一個數組組建為一個最大堆。具體代碼如下：
#include <stdio.h>
#include <stdlib.h>
void maxheapify( int array[], int root, int n )
{
int large;
int tmp;
if ( 2 * root + 1 > n -1 )
return;
else if ( 2 * root + 1 == n - 1)
{
if ( array[2 * root + 1] > array[root] )
{
tmp = array[2 * root + 1];
array[2 * root + 1] = array[root];
array[root] = tmp;
return;
}
return;
}
if ( array[2 * root + 1] < array[2 * root + 2] )
large = 2 * root + 2;
else
large = 2 * root + 1;
if ( array[root] < array[large] )
{
tmp = array[root];
array[root] = array[large];
array[large] = tmp;
maxheapify( array, large, n );
}
return;
}
void buildmaxheap( int array[], int n )
{
int i;
for ( i = (n - 2) / 2; i >= 0; i-- )
{
maxheapify( array, i, n );
}
return;
}
void heapsort( int array[], int n )
{
int i, tmp, j;
buildmaxheap( array, n );
for ( i = n - 1; i >= 0; i-- )
{
tmp = array[i];
array[i] = array[0];
array[0] = tmp;
maxheapify( array, 0, i );
}
}
int main()
{
int array[7] = {1, 3, 2, 5, 4,2,7};
int i;
heapsort( array, 7 );
for ( i = 0; i < 7; i++ )
printf( "%d ", array[i] );
return 0;
}復雜度分析，maxheapify()復雜度為O(logn)，buildmaxheap()復雜度為O(n*logn)，總復雜度為O(n*logn)，不管好壞。
三、插入排序
設想玩撲克時摸牌的過程，左手拿牌，右手取牌，每取過一張牌之後將此牌插入左手牌中的合適位置，按從小到大排列。對一個數組也是如此，從左到右遍歷數組，然後對每一個元素，插入到其之前的合適位置。具體代碼如下：
#include <stdio.h>
#include <stdlib.h>
void insertsort( int array[], int n )
{
int i, j, p;
for ( i = 0; i < n; i++ )
{
p = array[i];
for ( j = i - 1; j >= 0; j-- )
{
if ( p < array[j] )
{
array[j + 1] = array[j];
array[j] = p;
}
else
break;
}
}
return;
}
int main()
{
int i;
int array[5] = {1,2,5,4,3};
insertsort( array, 5 );
for ( i = 0; i < 5; i++ )
{
printf( "%d ", array[i] );
}
return 0;
}復雜度為O(n^2)。
四、冒泡排序
不多說~
五、歸並排序
設想手裡有兩堆撲克牌，分別是排好序的，將這兩堆撲克牌按順序排列的過程就是一個merge()的過程，mergesort()是一個遞歸的過程，具體代碼如下：
#include <stdio.h>
#include <stdlib.h>
void merge( int array[],int p, int q, int r )
{
int i = p;
int j = q;
int k = 0;
int * array_res = (int *)malloc( sizeof( int ) * (r - p + 1) );
while ( i <= q - 1 && j <= r )
{
if ( array[i] <= array[j] )
{
array_res[k] = array[i];
//printf( "%d", array_res[k] );
//return;
i++;
k++;
}
else if ( array[i] > array[j] )
{
array_res[k] = array[j];
j++;
k++;
}
}
if ( i > q - 1 )
{
while ( k < r - p + 1 )
{
array_res[k] = array[j];
k++;
j++;
}
}
for ( i = 0; i < r - p + 1; i++ )
{
array[p + i] = array_res[i];
}
return;
}
void mergesort( int array[], int m, int n )
{
if ( m == n )
return;
else
{
int r = ( n + m ) / 2;
mergesort( array, m, r );
mergesort( array, r + 1, n );
merge( array, m, r + 1, n );
}
}
int main()
{
int array[6] = {2,2,3,2,4,6};
mergesort( array, 0, 5 );
int i;
for ( i = 0; i < 6; i++ )
printf( "%d ", array[i] );
return 0;
}時間復雜度為O(n*logn)，額外空間復雜度為O(n)。
本文出自 “sdu_IS” 博客，請務必保留此出處http://hychuanshuo.blog.51cto.com/2724628/1274647
