排序问题
稳定排序、非稳定排序
如果ai = aj, 排序之后ai和aj的相对位置没有发生改变,这就是稳定排序。
如果发生了改变,那么就这种排序就是一类非稳定的排序。而稳定排序有三种需要讲
插入排序、冒泡排序、归并排序,除了对排序进行稳定和非稳定的排序,还可以这样分类,一类是内部排序一类是外部排序
插入排序:
具像化:在火车站排队买票,一个壮汉,从后面开始往后吧啦人,插队,弱小的扒拉到后面去,而发现前面的性质太强了,巴拉不动了,就成功进行了排队。
- 将数组分为“已排序区”和“待排序区”
- 将已经排序的区域后面的一个元素,向前插入到“待排序区”中
- 直到“待排序区”没有元素的时候为止。
void insert_sort(int *num, int n) {
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && num[j] < num[j - 1]; j--) {
swap(num[j], num[j - 1]);
}
}
}
冒泡排序:
也是将数组分为“已排序区”和“待排序区”,
从头到尾扫描,待排序区,若前面的元素比后面元素大,则交换(结果相当于保留待排序区的最大值)
放到已排序区的前一个位置上
每一轮都会将待排序区中国呢最大的放到已排序区的开头
直到待排序区没有元素为止
从头到尾扫描“待排序区”,若前面的元素比后面元素大,则交换
每一轮都会将待排序
void bubble_sort(int *num, int n) {
for (int
}
归并排序:
我拿到一组无序的数组序列的时候,我要对当前的数组进行排序,等价于可以将当前的数组分为两部分,分别进行排序,而我这两部分的数组,每一段都分别排好序之后,如果希望对数组进行整体的排序,我需要进行合并的操作,因为每一段数组,都市有序的,我去比较两个指针对应的指针谁大谁小,谁小就先放进去,这就和我每一个段的自然长度是有关系的,这就是对两个有序的数组进行河滨的操作,比如左边是m,有边是n,合并操作就是O(m+n),我们将两个大问题,分解成两个小问题,因为元素特别多,所以我可以继续向下区分,直到我发现每次都排序两个元素。
直到当前的规模足够小,将规模排好序,如此,我就可以找到数组对应的序列对应什么样子,我应该对两边的序列对应什么样子,
也就是说,我要进行logN次合并,而每一次的合并的时间复杂度为N *logN;
我们需要看到,将大的数组,每次分成两段进行分别排序,这就叫做二路归并,而事实上,还有k路归并,每次对于k路归并而言,每一次可以分成2路归并,进行归并))
这三个排序中,插入排序、冒泡排序是内部排序,而归并排序是外部排序。
我们的程序是在cpu中执行的,我先需要一段连续的空间,进行整体加载到内存,才可以整体去排序
如果我的内存现在只有4G,然后我发现当前的数据大小为40G,一个内存口最高16G,我需要分段去进行排序,我可以给它分成20个部分,每个部分2G,每两G拷贝一次,拍一次序,最后我就得到20组排好序的数据
归并排序的实现
在循环的内部,每次找到一个适合插到已经排序部分的最后的元素,而且可选的元素只有左半部分当前.
如果左半部分还有元素等待插入,并且,要么右半边的部分已经没有元素待插入了,要么左半部分待插入的元素的关键字不比右半部分的大,那么将左半部分的元素插入temp中;
否则,就把右半部分等待插入的元素放到temp的最后,并且让y + 1。 参考上面的代码,把这个逻辑写到else里面
if (x <= mid && ( y > r || data[x] <= data[y])) {
}
在工业上往往需要借用k路归并解决大型数据问题,做一个树
冒泡排序
- 升序排列
- 降序排列
外层循环(i)从0 ~ n - 1
里层循环(j)从 0 ~ n - 1- i
这样,发现里层循环随着i的增大都会变小,如果这一次我发现,j结束了,而且不需要交换大小了,那么就说明我这个排序结束了
选择排序
没次从线性表的待排序区域选择关键字最小的元素,把它放在已经排序区域的最后,因为每一趟排序可以让待排序区域减少一个,所以总共需要(n - 1)趟操作,
可以使用堆来优化,可以变小一点
#define TEST(arr, n, func, args...) {\
int *num = (int *)malloc(sizeof(int)*n);\
memcpy(num, arr, sizeof(int) * n);\
output(num, n);\
printf("%s = ", #func);\
func(args);\
ouput(num, n);\
free(num);\
}
//main函数中,arr是做好的数组(随机):
TEST(arr, max_op, insert_sort, num, max_op);
TEST(arr, max_op, bubble_sort,num, max_op);
TEST(arr, max_op, merge_sort, num, 0, max_op - 1);
我之所以用,num,是因为我不要改变sort的原来的数组
推荐阅读
-
studio碰到问题:java.lang.UnsatisfiedLinkError解决办法
-
ASP.NET基于Ajax的Enter键提交问题分析
-
asp.net中使用 Repeater控件拖拽实现排序并同步数据库字段排序
-
IOS 开发之实现取消tableView返回时cell选中的问题
-
android的RecyclerView实现拖拽排序和侧滑删除示例
-
iOS中指纹识别常见问题汇总
-
Android ScrollView嵌套ExpandableListView显示不正常的问题的解决办法
-
解决eclipse启动时报错Failed to create the Java Virtural Machine.问题的方法
-
php时间计算相关问题小结
-
解决 INSTALL FAILED CONFLICTING PROVIDER的问题方法