`
836811384
  • 浏览: 542246 次
文章分类
社区版块
存档分类
最新评论

基本算法和数据结构回顾(1)–排序

 
阅读更多

基本算法和数据结构回顾(1)–排序

作者:gaopenghigh,转载请注明出处。(原文地址)


个人感觉,学习算法和数据结构后一段时间,往往会忘掉很多东西,于是我给自己写了这 个回顾系列,什么东西想不起来时就翻看一下。

排序

如果存在多个排序码相同的记录,经过排序后,相同排序码记录的相对次序如果保持不变 ,则称这种排序方法是稳定的,对应Linux系统中sort命令的-s--stable参数。

插入排序

插入排序的基本方法是,每一步将一个待排序的记录,按其排序码大小,插到前面已经排 序的数据中的适当位置,直到全部插入完成为止。

直接插入排序

直接插入排序就是从第二个数据开始,和前面的所有数据比较,使前面的数据都是有序的 ,时间复杂度最好情况下是O(n),最坏情况下是O(n^2)。

二分法插入排序

通过二分法比较,平均复杂度为O(n^2)。

Shell排序

首先取一个整数d1 < n,把全部记录分成 d1 个组,所有距离为 d1 的倍数的记录放在 一组中,先在各组内排序,然后取d2 < d1重复上述分组和排序工作,直到d1 = 1,即 所有记录放在一组中为止。

Shell排序的时间复杂度大约是O(n^1.3)。

选择排序

选择排序的基本方法是:每步从待排序的记录中选出排序码最小的记录,顺序放在已经排 序的记录序列的后面,直到全部排完。

直接选择排序

就是“选择排序”的最基本语义的定义。时间复杂度为O(n^2)。

堆排序

使用一个堆存放未排序的数据,每次从堆中取出堆顶数据放到已排序数据后面,然后重新 调整堆,再取新的堆顶数据,直到堆中元素个数为0。

堆排序的时间复杂度为O(nlog2(n))。

交换排序

交换排序的基本方法是:两两比较待排序记录,如果不满足顺序要求则交换,直到全部满 足为止。

冒泡排序

冒泡排序通过相邻记录之间的比较和交换,使较大的逐步向后移动,而较小的向前移动, 每一趟冒泡后,最大的元素就会在最后,然后再对之前的数据进行一次冒泡,如果某一趟 冒泡中没有发生数据交换,说明数据已经排序好了。

当文件是正序时,显然时间复杂度为O(n),最坏时间复杂度为O(n^2)。

快速排序

快速排序的基本思想是:在待排序的n个记录中任意取一个记录为分区标准,把所有小于该 记录的移动到左边,大于该记录的移动的右边,称之为一趟排序;然后,对前后两个子序 列分别重复上述过程。

void swap(int v[], int i, int j) {
    int tmp;
    tmp = v[i];
    v[i] = v[j];
    v[j] = tmp;
}

/* 快速排序,对v[left] ... v[right]进行排序 */
void qsort(int v[], int left, int right) {
    int i, last;
    if (left >= right)
        return;

    /* 取中间一个元素为划分子集的元素, 并且把它和第一个元素交换 */
    swap(v, left, (left + right)/2);
    /* last表示的位置是其左边(包括它自己)的所有元素都小于特定元素 */
    /* 首先把last定位到开头,然后逐个比较元素是否小于特定元素 */
    /* 如果小于的话,就把它和last的下一位交换,同时last增加1 */
    /* 这样仍然满足last以及last之前的所以元素都小于特定元素 */
    last = left;
    /* 由于之前已经把特定元素放到开头了,所以从第二个元素开始和v[left]比较 */
    for (i = left+1; i <= right; i++)
        /* 如果小于的话,就把它和last的下一位交换,同时last增加1 */
        if (v[i] < v[left])
            swap(v, ++last, i);
    /* 注意,一开始的时候我们是把特定元素放到第一项的, 而last表示的是小于 */
    /* 特定元素的最后一项,现在交换它们的位置,也就是把特定元素放到中间 */
    /* 左边的都小于它,右边的都大于它 */
    swap(v, left, last);

    /* 对剩下的两部分进行同样的操作 */
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

当待排序记录已经排序时,用快速排序算法的执行时间最长。最坏情况下时间复杂度是 O(n^2),平均是O(nlog2(n))。快速排序是不稳定的。

分配排序

分配排序的思想是把排序码分解成若干部分,然后通过对各个部分排序码的分别排序,最 终达到整个排序码的排序。

考虑排序扑克牌,那么可以按照花色先分成4部分,黑-红-梅-方,然后再在各个部分内部 排好序。

对于数字,可以先按照个位排序,然后按照十位排序,依次类推。

归并排序

归并排序的主要思想是:把待排序的文件分成若干个子文件,先将每个子文件内的记录排 序,再将已排序的子文件合并,得到完全排序的文件。合并时开始只要比较各子文件第一 个记录的排序码,排序码最小的记录为排序后的第一个记录,取出该记录,继续比较各子 文件的第一个记录,找出排序后的第二个记录,如此反复,经过一次扫描,得到排序结果 。

/*
 * 归并排序
 */

/*
 * v[row]到r[m]和r[m+1]到r[high]是存储在同一个数组中且相邻的两个有序的子文件
 * merge函数将这两个子文件合并成一个有序的文件,并存放在v1[low]到v1[high]中
 */
void merge(int v[], int v1[], int low, int m, int high) {
    int i = low;
    int j = m + 1;
    int k = low;
    /* 不断从两个有序文件中的第一个记录中选出最小的记录 */
    while ((i <= m) && (j <= high)) {
        if (v[i] <= v[j])
            v1[k++] = v[i++];
        else
            v1[k++] = v[j++];
    }
    /* 分别复制两个文件的剩余记录,事实上只会有一个文件有记录 */
    while (i <= m)
        v1[k++] = v[i++];
    while (j <= high)
        v1[k++] = v[j++];
}

/*
 * 一趟归并算法,对长度为n的v做一趟归并,结果放在v1中, seg表示子文件的长度
 * 子文件应该是:v[0]~v[seg-1], v[seg]~v[2*seg-1], ...
 * 要注意,最后一个的长度有可能小于seg
 */
void merge_pass(int v[], int v1[], int size, int seg) {
    int i = 0;
    int j = 0;
    /* 两个两个地对文件进行归并 */
    while (i + 2 * seg -1 < size) {
        merge(v, v1, i, i+seg-1, i+2*seg-1);
        i += 2 * seg;
    }

    if (i+seg-1 < size-1)    /* 剩下两个文件,其中一个长度可能小于seg */
        merge(v, v1, i, i+seg-1, size-1);
    else                  /* 只剩下最后一个文件,直接复制即可 */
        for (j=i; j<size; j++)
            v1[j] = v[j];
}

/*
 * 二路归并算法
 * 通过改变seg的大小一边一遍地对数据进行merge_pass
 */
void merge_sort(int v[], int size) {
    int *temp = malloc(size * sizeof(int));
    int seg = 1;
    while (seg < size) {
        /* 把v进行一趟归并,存放到temp中 */
        merge_pass(v, temp, size, seg);
        seg += seg;
        /* 增加seg的值后对temp进行一次归并,存放到v中 */
        merge_pass(temp, v, size, seg);
        seg += seg;
    }
    free(temp);
}

二路归并排序的时间复杂度是O(nlog2(n))。

JH, 2013-05-19


参考资料:




分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics