博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
算法竞赛之排序算法初入门
阅读量:4317 次
发布时间:2019-06-06

本文共 6527 字,大约阅读时间需要 21 分钟。

                            关于排序的一些知识点

    排序是计算机内经常进行的一种操作,其目的是将一组"无序"的记录序列调整为"有序"的记录序列。我们学习的排序是关于算法之中,对一些特定数据,按照一定的优先级顺序将数据及逆行合理化的排列,比如在最初学习C语言的时候,老师提到的冒泡排序、选择排序,这两个是基本的排序,原理也应该比较简单,其实最早接触到的就是两个数字比较大小,然后按升序或者降序排布的,这个应该是最早接触的排序了。

    既然排序这么重要,我们就学习一下一些常见的排序算法吧,由于本人能力有限,所以有什么介绍不好的地方,欢迎评论并共同进步。

 

例子:3 2 1 5 6 0 1 2 3 7

 

  1. 冒泡排序(此次降序): 需要(n-1)轮的操作,最后得到一个单调数组,将当前数组里面的第一个元素与之后的元素进行比较,若是当前元素小于被比较的元素,则进行交换,由于每次都是最大的先固定下来,像水里的气泡,离水面越近越大,所以称之为冒泡排序。运行结果如下图所示:

    代码:

    #include 
     int main() {          int array[10] = {
    3, 2, 1, 5, 6, 0, 1, 2, 3, 7};     int cnt = 0;     for(int i = 0; i < 9; i++) {         for(int j = i + 1; j < 10; j++)             if(array[i] < array[j]) {                 int temp = array[i];                 array[i] = array[j];                 array[j] = temp;             }         printf("Case %d:\n", ++cnt);         for(int j = 0; j < 10; j++)             printf("%d ", array[j]);         printf("\n");             }     return 0; }

     

     

  2. 选择排序(降序):这个应该就是C语言之中最早接触到的排序算法了吧,对一个大小为n的数组,总共需要n轮排序之后,会得到一个单调数组,而在每一轮里面,每次在当前元素与被比较元素之间判断,若是被比较元素较大,则记录当前被比较元素的值以及下标,当前一轮操作结束之后,则将当前元素与记录的元素进行交换。

    结果:

    代码:

    #include 
     int main() {          int array[10] = {
    3, 2, 1, 5, 6, 0, 1, 2, 3, 7};     int cnt = 0;     for(int i = 0; i < 9; i++) {         int max_ = array[i], index = i;         for(int j = i + 1; j < 10; j++)             if(max_ < array[j]) {                 max_ = array[j];                 index = j;             }             int temp = array[i];             array[i] = array[index];             array[index] = temp;         printf("Case %d:\n", ++cnt);         for(int j = 0; j < 10; j++)             printf("%d ", array[j]);         printf("\n");             }     return 0; }

     

     

    讲完这两个比较基本的排序算法之后,我们开始学习一些比较中级一点的排序方法吧。

     

    例子:3 2 1 5 6 0 1 2 3 7

     

    1. 快速排序算法:(升序)
      1. 先从数列中取出一个数作为基准数。
      2. 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
      3. 再对左右区间重复第二步,直到各区间只有一个数。

      注:我们找的基准数一般都是数组的第一个元素的值。

       

这里手动打印出第一次排序的过程(红色为虚拟的)

        原始数组:3 2 1 5 6 0 1 2 3 7

        然后选取基准数:3,将数字存入临时变量之中,然后数组就多出来了一个位置,之后开始操作。

第一次:i = 0, j = 9, x = 3;

    开始从右往左开始扫描到第一个小于3的数字,若是大等于的话,则j进行自减,然后第一次找到的是下标为7,值为2的数字,这时候的数组变为:

    2 2 1 5 6 0 1 3 3 7

    i         j

i = 0, j = 7, x = 3;

    然后从左到右扫描到第一个大等于3的数字,若是小于的话,则i进行自增,然后第一次找到的下标为1,值为2的数字,这时候的数组变为:

    2 2 1 3 6 0 1 5 3 7

i j

i = 1, j = 7, x = 3

重复操作,接下来只打印满足时候,当前数组的状态,若是不满足i <j ,则当前轮结束;

    2 2 1 1 6 0 3 5 3 7

i j

    2 2 1 1 3 0 6 5 3 7

         i j

2 2 1 1 0 3 6 5 3 7

         ij

这时候,第一轮的结果结束,可以看到, 在基准数3的左边全部小于3,在基准数3的右边全部大等于3.所以被拆分成两个数组:

    第一个是2 2 1 1 0,第二个是6 5 3 7.

当最后传进来的数组大小为1的时候,那么当前循环就结束操作。

具体的模拟过程这里就不进行打印了,看过第一轮的过程,应该会对快速排序有一个比较直观的感受,要是不是很懂的话,那么就多看几遍试试。

代码:

#include 
 void quick_sort(int* s, int l, int r) {          if (l < r) { int i = l, j = r, x = s[l]; while (i < j) { while(i < j && s[j] >= x)                 j--; if(i < j)                 s[i++] = s[j];               while(i < j && s[i] < x)                 i++; if(i < j)                 s[j--] = s[i]; } s[i] = x; quick_sort(s, l, i - 1); quick_sort(s, i + 1, r); } }  int main() {          int s[10] = {
3, 2, 1, 5, 6, 0, 1, 2, 3, 7};     quick_sort(s, 0, 9);     for(int i = 0; i < 10; i++)         printf("%d ", s[i]);     return 0; }

 

 

  1. 堆排序:堆排序还是基于二叉树的感觉,
    1. 根据数组元素创建一棵完全二叉树
    2. 先构造初始堆,需要从最后一个非叶子节点调节,保证每次得到的堆都满足父亲节点的值大于左右孩子节点的值;
    3. 将每次操作得到的根节点元素与当前堆中的最后一个元素进行交换,然后重复步骤(b),直到需要操作的元素大小为1时候,则已经完成了堆排序

过程:

1.先创建一棵完全二叉树:

2.构造初始堆:

 

3.开始重新调整,获取满足结果的堆结果:

    图1. 因为初始堆的根肯定是最大的,所以直接与最后一个元素进行交换

    图2,进行重新排序之后的结果

    图1                        图2 图2结果

排序结束,所以最后得到的数组顺序为:0 1 1 2 2 3 3 5 6 7

代码:

#include 
 void Heapfy(int A[],int idx,int max) {          int left=idx*2+1;     int right=left+1;     int largest=idx;     if(left
A[idx])         largest=left;     if(right
=0;--i)         Heapfy(A,i,len);     for(int i=len-1;i>=1;--i) {         int temp=A[0];         A[0]=A[i];         A[i]=temp;         Heapfy(A,0,i);     } }  int main() {          int arr[10] = {
3, 2, 1, 5, 6, 0, 1, 2, 3, 7};     int size = 10;     buildHeap(arr, size);     for(int i=0; i

 

 

3.归并排序:将数组进行拆分成小块的,保证每个块中的元素是有序的,然后将两两进行拼接,根据当前移动的数组所在的元素大小进行插入。

 

 

过程:

先将数组进行拆分成最小块:

 

然后将每个块内进行排序,两个块进行叠加的时候,用两个指针分别指向各自数组,然后在O(n)的时间复杂度就可以完成,然后拆分的时间是N(lg(n))

下面是进行叠加的过程:

 

 

代码:

#include
using namespace std; int n,a[30000],b[30000],cnt; void merge(int x,int y,int z){     int i=x,j=y+1,k=0;     while(i<=y&&j<=z){         if(a[i]

 

 

//(代码来源:斌神)

 

 

 

4.基数排序:根据当前位的数字,然后装入不同的数组,之前看一个例子,语言不知道怎么组织就是了(个人感觉基数排序应该是针对绝对值排序这种,即一个数组里面的元素应该是同号才对)

 

例子: 123 321 456 264 5329 21230 326

因为所有数组之中,最大的数字的长度为5,所以5次就可以得到一个单调数组。

 

第一轮(个位数)

0:21230

1:321

3:123

4:264

6:456 326

9:5329

结果: 21230 321 123 264 456 326 5329

 

 

第二轮(十位数)

2:321 123 326 5329

3:21230

5:456

6:264

结果:321 123 326 5329 21230 456 264

第三轮(百位数)

1:123

2:21230 264

3:321 326 5329

4:456

结果:123 21230 264 321 326 5329 456

第四轮(千位数)

0:123 264 321 326 456

1:21230

5:5329

结果:123 264 321 326 456 21230 5329

第五轮(万位数)

0: 123 264 321 326 456 5329

2: 21230

结果: 123 264 321 326 456 5329 21230

 

所以最后的结果是: 123 264 321 326 456 5329 21230

代码:

#include 
#include
 void ji_sort(int arr[], int ll, int n) {          int s = 1;     for(int t = 1; t <= ll; t++) {         int num[10][15];         int len[10];         memset(num, 0, sizeof(num));         memset(len, 0, sizeof(len));         for(int i = 0; i < n; i++){             int temp = arr[i] / s % 10;             num[temp][len[temp]++] = arr[i];         }         int l = 0;         printf("Case %d:\n", t);         for(int i = 0; i < 10; i++) {             if(len[i] != 0)                 printf("\n%d:", i);             for(int j = 0; j < len[i]; j++) {                 arr[l++] = num[i][j];                 printf(" %d", num[i][j]);                 }         }         printf("\n结果;");         for(int i = 0; i < n; i++)             printf("%d ", arr[i]);         printf("\n");         s *= 10;     } }  int main() {          int array[15], n, l = 0;     scanf("%d", &n);     for(int i = 0; i < n; i++){         scanf("%d", &array[i]);         int t = array[i], s = 0;         while(t) {             s++;             t/=10;         }         if(s > l)             l = s;     }     printf("%d\n", l);     ji_sort(array, l, n);     return 0; }

 

 

 

上面都是属于自己实现的算法,其实在c++里面已经对快速排序进行封装,提供了一个方法->sort()。还是建议平时做题的时候,直接使用系统提供的函数进行编写,不仅效率高,而且还不容易出错,当然了,这些算法平常时候还是要自己敲敲来熟悉一下。

原本是应该讲述qsort,但平常本人都是使用sort函数,而且也感觉会比qsort好用,如果想了解的话,这里仅仅是作为一个入门使用的,想多了解的话还是夺取看看博客之类的文章吧

Sort(arr, arr+n, cmp);

一般是三个参数,第一个参数代表着起始位置,第二个参数代表着结束为止,最后一个参数代表着排序规则。如果只写前面两个参数的话,那么就会采用默认的排序,即升序排序,若是遇到了自定义结构体的话,肯定是要写第三个参数,第三个参数的名称和你定义的函数体是要一致的。

 

大致的排序就说到这里,不懂的话可以群里直接问吧。

转载于:https://www.cnblogs.com/huaixiaohai2015/p/7191409.html

你可能感兴趣的文章
Common Subsequence(最长公共子序列)
查看>>
weighing scheme
查看>>
java_简单解析ArrayList_iterable
查看>>
hashlib和hmac
查看>>
设计类作品
查看>>
2014-04-19编程之美初赛题目及答案解析
查看>>
jmeter+ant+jenkins+mac 报告优化(三) 使用命令行执行jmeter方式生成多维度的图形化HTML报告...
查看>>
Android设计模式系列-适配器模式
查看>>
sshd登录攻击
查看>>
STL小代码之一
查看>>
捆绑安装浏览器:技术剖析搜狗输入法中的猫腻
查看>>
schema
查看>>
apache kafka配置中request.required.acks含义
查看>>
Core Instrumentation Events in Windows 7, Part 2
查看>>
sharepoint securityToken.svc 无法打开
查看>>
Jedis连接池的使用
查看>>
浏览器劫持(hijack)
查看>>
javascript设计模式--继承(上)
查看>>
九度OJ 1499 项目安排 -- 动态规划
查看>>
还原sqlserver2008 媒体的簇的结构不正确的解决方法
查看>>