算法基础-排序算法

/*
 * Insert sort algorithm.
 * O(n^2)
 *
 * 说明：该算法把要排序的元素分成，已排好的有序区和代排序区。
 *       然后在代排序区中拿一个元素插入到有序区中，使得有序区
 *       不断扩大，而代排序区不断减少。
 *
 */

int insert_sort(int a[], int num)
{
    int i, j, key;
   
    for (i = 1; i < num; i++) {
        // 取一个代排序元素作为当前元素
        key = a[i];
        // 把i之前大于a[i]的元素向后移动一个位置,注意边界;
        for (j = i; j > 0 && a[j-1] > key; j--) {
            a[j] = a[j - 1];
        }  
        // 在合适的位置安放当前元素,此时j就是合适的位置,因为j以前的元素都比当前元素小
        a[j] = key;
    }  
      
    return OK;
}

1.2 希尔排序
/*
 * Shell sort.
 */
int shell_sort(int a[], int len)
{
    int gap, i, j, temp;
       
    for (gap = len/2; gap > 0; gap /= 2) {  //gap 是增量
        for (i = gap; i < len; i++) {       //对增量值为gap的元素进行插入排序
            temp = a[i];
            for (j = i; j >= gap; j-=gap) {
                if (temp < a[j - gap])
                    a[j] = a[j - gap];
                else
                    break;
            }  
            a[j] = temp;
        }  
    }  
    return OK;
}

   分析: 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
  该方法实质上是一种分组插入方法。


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<v}
   4) 返回 quicksort(S1),继续v,继而quicksort(S2)
对于第3步枢纽元素的选择,选择好的枢纽元素将会大大提高程序的效率,所以如何选择好的枢纽元素,成为一个设计上的决策.
.如何选择枢纽元素?
  常用的想法是直接选择第一个元素作为枢纽元素,但是有时候第一个元素并不是最好的,会造成算法整体效率下降,这里<参考1>给出一种选择枢纽元素的策略:
 三数中值分割法选择枢纽元素: 即使用数组最左端和最右端以及中心元素三个元素的中间值作为枢纽元素.

  



待续...

参考书籍:
1,<<数据结构与算法分析>>  Mark Allen Weiss
2,<<数据结构>> 严蔚明 <<数据结构 c语言描述>> 高一凡
http://student.zjzk.cn/course_ware/data_structure/web/PAIXU/paixu8.2.2.1.htm