1)，即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
2, 交换排序
2.1 冒泡排序
/*
* 冒泡排序
* 每一趟把最大的元素沉到最后去.
*/
int bubble_sort(int a[], int len)
{
int i, j, tmp;
// 0...len是无序区
for (i = 0; i < len; i++) { //最多做len-1趟排序
for (j = len - 1; j > i; j--) { //对当前无序区a[i..len-1]自下向上扫描
if (a[j] < a[j-1]) { //把最小的元素交换到i位置,并把i加1
tmp = a[j];
a[j] = a[j-1];
a[j-1] = tmp;
}
}
}
return OK;
}
分析:由于该算法每趟都要经过n步的比较,而一共要进行n次这样的比较；所以时间复杂度为: O(n^2)
2.2 快速排序
快速排序是一种分治的递归算法.将数组S排序的基本算法由以下四步组成:
1) 如果S中元素个数是0或1,返回
2) 取S中任一元素v,称为枢纽元素
3) 将S分为两个不相交的集合,一个S1={x>v} 一个全S2={x
4) 返回 quicksort(S1),继续v,继而quicksort(S2)
对于第3步枢纽元素的选择,选择好的枢纽元素将会大大提高程序的效率,所以如何选择好的枢纽元素,成为一个设计上的决策.
.如何选择枢纽元素?
常用的想法是直接选择第一个元素作为枢纽元素,但是有时候第一个元素并不是最好的,会造成算法整体效率下降,这里<参考1>给出一种选择枢纽元素的策略:
三数中值分割法选择枢纽元素: 即使用数组最左端和最右端以及中心元素三个元素的中间值作为枢纽元素.
2.2.1 普通快速排序算法
说明：快速排序算法就是选择一个中心值v，并围绕这个值把数组分成两部分，
一部分是全部大于v的值，另一部分是全部小于v的值。然后再递归对直到全部的数组元素都排好序。
int partition(int a[], int p, int r)
{
int key;
int i, j;
//取一个基准值，注意这里可以优化。因为基准值的选取很重要，
//但这一版是直接选数组的最后一个元素作为基准值。
key = a[r];
printf("key=%d\n", key);
i = p - 1;
for (j = p; j <= r-1; j++) { //从i的后一个元素开始遍历
if (a[j] <= key) { // 若元素小于基准值
i += 1; //继续向后遍历
swap(a, i, j); //需要把j和i位置的值进行交换
}
}
swap(a, i + 1, r);
printarr(a, QLEN);
return i + 1;
}
int quicksort(int a[], int p, int r)
{
int q;
if (p < r) {
q = partition(a, p, r);
printf("q=%d\n", q);
quicksort(a, p, q - 1);
quicksort(a, q + 1, r);
}
}
int main(void)
{
int a[QLEN];
create_data(a, QLEN);
printarr(a, QLEN);
quicksort(a, 0, QLEN-1);
printarr(a, QLEN);
}
演示结果
说明：
(1) i和j是每次的i和j的值
(2) swap：说明发生一次交换
(3) key: 的值是本次的基准值
(4) q是：区分值
生成的数组：
41 91 57 32 83 4 68 25 3 80 #原始生成的数组
key=80
i=-1,j=0
swap: i=0,j=0
41 91 57 32 83 4 68 25 3 80
i=0,j=1
41 91 57 32 83 4 68 25 3 80
i=0,j=2
swap: i=1,j=2
41 57 91 32 83 4 68 25 3 80
i=1,j=3
swap: i=2,j=3
41 57 32 91 83 4 68 25 3 80
i=2,j=4
41 57 32 91 83 4 68 25 3 80
i=2,j=5
swap: i=3,j=5
41 57 32 4 83 91 68 25 3 80
i=3,j=6
swap: i=4,j=6
41 57 32 4 68 91 83 25 3 80
i=4,j=7
swap: i=5,j=7
41 57 32 4 68 25 83 91 3 80
i=5,j=8
swap: i=6,j=8
41 57 32 4 68 25 3 91 83 80
41 57 32 4 68 25 3 80 83 91
q=7
key=3
i=-1,j=0
41 57 32 4 68 25 3 80 83 91
i=-1,j=1
41 57 32 4 68 25 3 80 83 91
i=-1,j=2
41 57 32 4 68 25 3 80 83 91
i=-1,j=3
41 57 32 4 68 25 3 80 83 91
i=-1,j=4
41 57 32 4 68 25 3 80 83 91
i=-1,j=5
41 57 32 4 68 25 3 80 83 91
3 57 32 4 68 25 41 80 83 91
q=0
key=41
i=0,j=1
3 57 32 4 68 25 41 80 83 91
i=0,j=2
swap: i=1,j=2
3 32 57 4 68 25 41 80 83 91
i=1,j=3
swap: i=2,j=3
3 32 4 57 68 25 41 80 83 91
i=2,j=4
3 32 4 57 68 25 41 80 83 91
i=2,j=5
swap: i=3,j=5
3 32 4 25 68 57 41 80 83 91
3 32 4 25 41 57 68 80 83 91
q=4
key=25
i=0,j=1
3 32 4 25 41 57 68 80 83 91
i=0,j=2
swap: i=1,j=2
3 4 32 25 41 57 68 80 83 91
3 4 25 32 41 57 68 80 83 91
q=2
key=68
i=4,j=5
swap: i=5,j=5
3 4 25 32 41 57 68 80 83 91
3 4 25 32 41 57 68 80 83 91
q=6
key=91
i=7,j=8
swap: i=8,j=8
3 4 25 32 41 57 68 80 83 91
3 4 25 32 41 57 68 80 83 91
q=9
3 4 25 32 41 57 68 80 83 91
2.2.2 随机化版本的快速排序
// 随机选择标准值
int rnd_partition(int a[], int p, int r)
{
int i;
srand((unsigned int)time(NULL));
i = rand() % (r-p+1)+p; //注意随机值的选择
swap(a, r, i);
return partition(a, p, r);
}
//排序利用随机选择的值排序
void rnd_qsort(int a[], int p, int r)
{
int q;
if (p < r) {
q = rnd_partition(a, p, r);
rnd_qsort(a, p, q - 1);
rnd_qsort(a, q + 1, r);
}
2.2.3 改进的快速排序算法1
//尾部递归+随机标准值
//为了减少压栈的层数，使用尾部递归法
void nore_qsort(int *a, int p, int r)
{
int q;
while (p < r) { //注意这里是while(p < r)不是if了
q = rnd_partition(a, p, r);
rnd_qsort(a, p, q - 1);
p = q + 1;
}
}
2.2.3 改进的快速排序算法2
//优化的快速排序
// 三数取中确定基准值
int median_partition(int A[], int p, int r)
{
int range = r - p + 1;
int med1 = p + rand() % range;
int med2 = p + rand() % range;
int med3 = p + rand() % range;
int med = (A[med1] < A[med2]) ?
(A[med2] < A[med3] ? med2 : (A[med1] < A[med3] ? med3 : med1)):
(A[med1] < A[med3] ? med1 : (A[med2] < A[med3] ? med2 : med3));
swap(A, med, r);
return partition(A, p, r);
}
void median_quick_sort(int A[], int p, int r)
{
if (p < r) {
int q = median_partition(A, p, r);
median_quick_sort(A, p, q - 1);
median_quick_sort(A, q + 1, p);
}
}
2.3 stooge排序
//该排序算法把待排序的数组分成3个部分，而不是象快速排序算法分成两个部分。
//该算法也使用了递归，据《算法导论》上描述，该算法是三个教授提出的。
void stooge_sort(int a[], int i, int j)
{
int k;
if (a[i] > a[j])
swap(a, i, j);
if (i + 1 >= j)
return;
k = (j - i + 1)/3;
stooge_sort(a, i, j-k);
stooge_sort(a, i+k, j);
stooge_sort(a, i, j-k);
}
待续...
参考书籍:
1,<<数据结构与算法分析>> Mark Allen Weiss
2,<<数据结构>> 严蔚明 <<数据结构 c语言描述>> 高一凡
