基本算法和数据结构回顾(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
参考资料:
分享到:
相关推荐
【课程简介】 本课程适合所有需要弥补数据结构或对数据结构感兴趣的同学,课件内容制作精细,由浅入深,适合入门或进行知识回顾。 【完整课程列表】 ...数据结构与算法 数据结构与C语言 第8章 排序(共223页).ppt
其中包括了线性表、栈和队列、串和数组、树和图等数据结构的操作、排序等,非常适合进阶级的...其中需要的预备知识数学中的集合、对数、递归等的回顾,还有C#语法中的接口和泛型的温习,从而更快的接受数据结构和算法。
【课程简介】 本课程适合所有需要弥补数据结构或对数据结构感兴趣的同学,课件内容制作精细,由浅入深,适合入门或进行知识回顾。 【完整课程列表】 ...数据结构与算法 数据结构与C语言 第8章 排序(共223页).ppt
数据结构、算法与应用_C++语言描述排序总结,关注排序
【课程简介】 本课程适合所有需要弥补数据结构或对数据结构感兴趣的同学,课件内容制作精细,由浅入深,适合入门或进行知识回顾。 【完整课程列表】 ...数据结构与算法 数据结构与C语言 第8章 排序(共223页).ppt
【课程简介】 本课程适合所有需要弥补数据结构或对数据结构感兴趣的同学,课件内容制作精细,由浅入深,适合入门或进行知识回顾。 【完整课程列表】 ...数据结构与算法 数据结构与C语言 第8章 排序(共223页).ppt
【课程简介】 本课程适合所有需要弥补数据结构或对数据结构感兴趣的同学,课件内容制作精细,由浅入深,适合入门或进行知识回顾。 【完整课程列表】 ...数据结构与算法 数据结构与C语言 第8章 排序(共223页).ppt
【课程简介】 本课程适合所有需要弥补数据结构或对数据结构感兴趣的同学,课件内容制作精细,由浅入深,适合入门或进行知识回顾。 【完整课程列表】 ...数据结构与算法 数据结构与C语言 第8章 排序(共223页).ppt
【课程简介】 本课程适合所有需要弥补数据结构或对数据结构感兴趣的同学,课件内容制作精细,由浅入深,适合入门或进行知识回顾。 【完整课程列表】 ...数据结构与算法 数据结构与C语言 第8章 排序(共223页).ppt
【课程简介】 本课程适合所有需要弥补数据结构或对数据结构感兴趣的同学,课件内容制作精细,由浅入深,适合入门或进行知识回顾。 【完整课程列表】 ...数据结构与算法 数据结构与C语言 第8章 排序(共223页).ppt
【课程简介】 本课程适合所有需要弥补数据结构或对数据结构感兴趣的同学,课件内容制作精细,由浅入深,适合入门或进行知识回顾。 【完整课程列表】 ...数据结构与算法 数据结构与C语言 第8章 排序(共223页).ppt
道01数据结构和算法绪论. mp402_谈谈算法. mp4 西03_时间复杂度和空间复杂度.mp404_时间复杂度和空间复杂度2.mp405_时间复杂度和空间复杂度3.mp4险06线性表. mp407_线性表2. mp408_线性表3. mp4品09_ 线性表4. mp...
第1章向读者介绍数据结构作为数据集合的概念。介绍线性和非线性集合的概念。示范说明了Collection类。本章还介绍泛型编程的概念。泛型编程允许程序员编写一个类或一种方法,并且把它用于众多数据类型。泛型编程是C#...
本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一...
本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一...
01-001数据结构的概念和基本术语、抽象数据类型的表示与实现 01-002算法设计的要求、算法效率的度量 02-001线性表的类型定义 02-002线性表的顺序表示与实现、线性表的基本操作 02-003单链表的创建与操作、加工型...
5.1 数据对象和数据结构 5.2 线性表数据结构 5.2.1 抽象数据类型linearList 5.2.2 抽象类linearList 5.3 数组描述 5.3.1 描述 5.3.2 变长一维数组 5.3.3 类arrayList 5.3.4 C++迭代器 5.3.5 arrayList的一个迭代器 ...
本专栏记录研究生期间算法学习过程,从基础回顾到算法落地。算法学习范围为蓝桥杯官网提供的命题范围: 计算机算法:枚举、排序、搜索、计数、贪心、动态规划、图论、数论、博弈论*、概率论*、计算几何*、字符串算法...
本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一...