? ? ??學習了《數據結構與算法分析-C語言描述》的第7章關于排序的章節,記錄一下了^_^
1. 插入排序
? ? ? 插入排序由N-1趟排序組成,對于P=1趟到P=N-1趟,插入排序保證位置0到位置P的元素為已排序狀態,插入排序利用了這樣的事實,位置0到P-1的位置上的元素是已經排好
序的時間復雜度為O(N^2)
~~~
void Insert(int a[], int n)
{
int i, j, t;
for(i = 1; i < n; i++)
{
t = a[i];
for(j = i; j>0 && a[j-1]>t; j--)
a[j] = a[j-1];
a[j] = t;
}
}
~~~
2. 希爾排序
? ? ? 希爾排序是對插入排序的一種改進......

? ? ??默認初始inc增量是n/2
~~~
void Shellsort(int a[], int n)
{
int i, j, inc, t;
for(inc = n/2; inc > 0; inc /= 2)
{
for(i = inc; i < n; i++)
{
t = a[i];
for(j = i; j >= inc; j -= inc)
{
if(t < a[j-inc])
a[j] = a[j-inc];
else
break;
}
a[j] = t;
}
}
}
~~~
3. 堆排序
~~~
static void _swap(int *x, int *y)
{
int t;
t = *x;
*x = *y;
*y = t;
}
#define LeftChild(i) (2*(i))
static void _pass(int a[], int i, int n)
{
int child, t;
for(t = a[i]; LeftChild(i) < n; i = child)
{
child = LeftChild(i);
if(a[child+1] > a[child])
child++;
if(child != n-1 && t < a[child])
a[i] = a[child];
else
break;
}
a[i] = t;
}
void Heapsort(int a[], int n)
{
int i;
for(i = n/2; i >= 0; i--)
_pass(a, i, n);
for(i = n-1; i > 0; i--)
{
_swap(&a[0], &a[i]);
_pass(a, 0, i);
}
}
~~~
4. 歸并排序
? ? ??該算法基本的操作是合并兩個已排序的表。這兩個表示已排序的,所以若將輸出到第三個表中則該算法可以通過對輸入數據一趟排序來完成。
雖然歸并排序的運行時間是O(log(N)),但是它很難用于主存排序,主要問題在于合并兩個排序的表需要線性附加內存。
~~~
static void _merge(int a[], int tmpa[], int lpos, int rpos, int rend)
{
int n, lend, tmppos, i;
lend = rpos - 1;
n = rend - lpos + 1;
tmppos = lpos;
while(lpos <= lend && rpos <= rend)
{
if(a[lpos] <= a[rpos])
tmpa[tmppos++] = a[lpos++];
else
tmpa[tmppos++] = a[rpos++];
}
while(lpos <= lend)
tmpa[tmppos++] = a[lpos++];
while(rpos <= rend)
tmpa[tmppos++] = a[rpos++];
for(i = 0; i < n; i++, rend--)
a[rend] = tmpa[rend];
}
static void _msort(int a[], int tmpa[], int lpos, int rpos)
{
int mid;
if(lpos < rpos)
{
mid = (lpos +rpos) / 2;
_msort(a, tmpa, lpos, mid);
_msort(a, tmpa, mid+1, rpos);
_merge(a, tmpa, lpos, mid+1, rpos);
}
}
void Mergesort(int a[], int n)
{
int *tmpa;
if(n < 2)
return;
tmpa = (int *)malloc(n * sizeof(int));
if(tmpa != NULL)
{
_msort(a, tmpa, 0, n-1);
free(tmpa);
}
else
printf("No space exist.\n");
}
~~~
5 快速排序
? ? ??快速排序是在實踐中最快的已知排序方法,它的平均運行時間為O(log(N))。
~~~
int _pass(int a[], int low, int high)
{
int t;
t = a[low];
if(low < high)
{
while(low < high)
{
while(low < high && a[high] >= t)
high--;
a[low] = a[high];
while(low < high && a[low] <= t)
low++;
a[high] = a[low];
}
a[low] = t;
}
return low;
}
void _quickpass(int a[], int low, int high)
{
int mid;
if(low < high)
{
mid = _pass(a, low, high);
_quickpass(a, low, mid-1);
_quickpass(a, mid+1, high);
}
}
void Quicksort(int a[], int n)
{
_quickpass(a, 0, n-1);
}
~~~
6. 外部排序
? ? ??以上的排序算法都是將輸入數據裝入內存,而在一些應用中,他們的輸入數據量太大裝不進內存,這就要用到外部排序,它用來處理很大的輸入的。
合并時外部排序的中心思想。^_^