学习了《数据结构与算法分析-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. 外部排序
以上的排序算法都是将输入数据装入内存，而在一些应用中，他们的输入数据量太大装不进内存，这就要用到外部排序，它用来处理很大的输入的。
合并时外部排序的中心思想。^_^
