五种基本排序

Love The Way You Lie 2022-08-19 13:11 102阅读 0赞

最近在看数据结构，想把几个简单的排序在过一遍，发现还没那么容易，最简单的冒泡排序代码没那么容易敲出来。下面把5种排序复习一下：

1. 冒泡排序：

冒泡排序是最简单也是最常用的排序方法。其基本思想是（以升序为例）：将序列看成一排竖着的气泡。最后一个元素与倒数第二个元素进行比较，小的往前拱，再将倒数第二个元素与倒数第三个元素比较，小的往前拱，...这样一次外循环后，第一个元素就是序列最小的元素。n次外循环后就将序列排列好了。具体的程序如下：

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  <span style="font-size:14px;"> int temp;  
2.    
3.   int num=0;  
4.    
5.   int a\[10\]=\{13,2,5,18,7,12,9,10,15,6\};  
6.    
7.   for(int i=0;i<10;i++)  
8.    
9.    for(int j=9;j>=i;j--)  
10.   
11.   \{  
12.   
13.    num++;  
14.   
15.    if (a\[j\]<a\[j-1\])  
16.   
17.    \{  
18.   
19.     temp=a\[j\];  
20.   
21.     a\[j\]=a\[j-1\];  
22.   
23.     a\[j-1\]=temp;  
24.   
25.    \}  
26.   
27.   \}  
28.   
29.     
30.   
31.  for (i=0;i<10;i++)  
32.   
33.  \{  
34.   
35.   printf("%d  ",a\[i\]);  
36.   
37.  \}  
38.   
39.  printf("\\n");  
40.   
41.  printf("%d\\n",num);  
42.   
43.     
44.   
45. </span>

改进后的冒泡排序算法：

冒泡排序是每次将最小的数往上推（通过由下往上的两两比较)，但有的时候序列已经有一定顺序了，每次再去比较就会浪费时间。所以可以设立一个flag，当某一次比较没有数据发生交换时，证明已经排好了，后面的就不去用再继续了。具体程序如下：

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  <span style="font-size:14px;">int temp;  
2.    
3.   int num=0;  
4.    
5.   bool flag=false;  
6.    
7.   int a\[10\]=\{13,2,5,18,7,12,9,10,15,6\};  
8.    
9.   for(int i=0;i<10 && !flag;i++)  
10.   
11.  \{  
12.   
13.   flag=true;  
14.   
15.   for(int j=9;j>=i;j--)  
16.   
17.   \{  
18.   
19.    flag=false;  
20.   
21.    num++;  
22.   
23.    if (a\[j\]<a\[j-1\])  
24.   
25.    \{  
26.   
27.     temp=a\[j\];  
28.   
29.     a\[j\]=a\[j-1\];  
30.   
31.     a\[j-1\]=temp;  
32.   
33.    \}  
34.   
35.   \}  
36.   
37.  \}    
38.   
39.      for (i=0;i<10;i++)  
40.   
41.   \{  
42.   
43.    printf("%d  ",a\[i\]);  
44.   
45.   \}  
46.   
47.  printf("\\n");  
48.   
49.  printf("%d\\n",num);  
50.   
51. </span>

2.直接插入排序：

直接插入排序的思想是：把一个数插入到一个有序序列中，原先的序列已经是排好的了，所以要先要找到该元素的位置，将原先的序列移动，然后再将数字插入。代码如下：

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  <span style="font-size:14px;">if(Is\_Full(pArr))  
2.    
3.    return false;  
4.    
5.   if(pos<1 || pos>pArr->cnt+1)  
6.    
7.    return false;  
8.    
9.   for (int i=pArr->cnt-1;i>=pos-1;i--)  
10.   
11.      pArr->pBase\[i+1\]=pArr->pBase\[i\];  
12.   
13.  pArr->pBase\[pos-1\]=val;  
14.   
15.  pArr->cnt++;  
16.   
17. </span>

直接插入也可以改进，改进后的插入排序时边比较边移动的，当找到合适的位置时就直接插入。代码如下：

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  <span style="font-size:14px;">if(Is\_Full(pArr))  
2.    
3.    return false;  
4.    
5.   int pos=pArr->cnt-1;  
6.    
7.   for (int i=pos;i>=0;i--)  
8.   \{  
9.    
10.   if (val<pArr->pBase\[i\])  
11.   
12.   \{  
13.   
14.    pArr->pBase\[i+1\]=pArr->pBase\[i\];  
15.   
16.   \}  
17.   
18.   else  
19.   
20.   \{  
21.   
22.    pArr->pBase\[i+1\]=val;  
23.   
24.    pArr->cnt++;  
25.   
26.          return true;   
27.   
28.   \}  
29.   
30.  \}  
31.   
32.  pArr->cnt++;  
33.   
34. </span>

3.快速排序：

快速排序是效率比较高的排序算法，其又细分为几种，不过基本思想是一样的。只要思想是：选定序列的第一个数，先找到该数的真实位置，然后将序列以这个数分为两个部分，左边又选定第一个数，找到该数的真实位置，右边也选定第一个数，找到该数的真实位置，....不断找到子序列第一个数的真实位置，实际上是一个递归的过程。至于第一个数的真实位置时如何确定的，是同过两个标记来实现的，每次都与这个数比较进行移动或者赋值,具体见代码：

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  <span style="font-size:14px;">\#include <stdio.h>  
2.    
3.  void QuickSort(int\* a,int low,int high); //数组名和指针可以互用  
4.    
5.  int FindPos(int\* a,int low,int high); //找到第一个元素的真实位置  
6.    
7.  int main()  
8.    
9.  \{  
10.   
11.  int a\[6\]=\{1,3,0,2,5,4\};  
12.   
13.  QuickSort(a,0,5); //low 为 0，high 为 5  
14.   
15.  for(int i=0;i<6;i++)  
16.   
17.   printf("%d ",a\[i\]);  
18.   
19.  printf("\\n");  
20.   
21.  return 0;  
22.   
23. \}  
24.   
25. //递归实现  
26.   
27. //快速排序的思想：先找到第一个元素的真实位置，在将其左右两部分分成两个序列，继续查找序列的第一个元素的真实位置  
28.   
29. void QuickSort(int\* a,int low,int high)  
30.   
31. \{  
32.   
33.  int pos;  
34.   
35.  if (low<high)  
36.   
37.  \{  
38.   
39.   pos=FindPos(a,low,high);  
40.   
41.   QuickSort(a,low,pos-1);  
42.   
43.   QuickSort(a,pos+1,high);  
44.   
45.  \}  
46.   
47. \}  
48.   
49. int FindPos(int\*a,int low,int high)  
50.   
51. \{  
52.   
53.  int val=a\[low\]; //临时变量val存储第一个元素的值，用来比较  
54.   
55.  while (low<high)  
56.   
57.  \{  
58.   
59.   while (low<high && a\[high\]>val) //右部分比val大就移动  
60.   
61.    high--;   
62.   
63.   a\[low\]=a\[high\]; //否则就把值赋给a\[low\]  
64.   
65.   while(low<high && a\[low\]<val) //左半部分比val小就移动  
66.   
67.    low++;  
68.   
69.   a\[high\]=a\[low\]; //否则就赋给a\[high\]  
70.   
71.  \}  
72.   
73.  a\[low\]=val; //最后low于high就指向了第一个元素的真实位置  
74.   
75.  return low;  
76.   
77. \}  
78.   
79. </span>

4.选择排序

选择排序与冒泡排序类似；其基本思想是：假设开始有0个有序数和n个无序数，经过一次排序后就变成了1个有序数和n-1个有序数了...，每一次排序都使有序数的个数+1，无序数的个数减一。主要代码如下：

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  <span style="font-size:14px;">int temp,b;  
2.   int num=0;  
3.   int a\[10\]=\{13,2,5,18,7,12,9,10,15,6\};  
4.      for(int i=0;i<10;i++)  
5.   \{  
6.    temp=i;  
7.    for(int j=i+1;j<10;j++)  
8.     if(a\[temp\]>a\[j\])  
9.     \{  
10.        temp=j;  
11.    \}  
12.   if (i!=temp)  
13.   \{  
14.    num++; //当n较小时，num的次数比冒泡排序小  
15.    b=a\[temp\];  
16.    a\[temp\]=a\[i\];  
17.    a\[i\]=b;  
18.   \}  
19.     \}  
20. </span>

\*当n的次数较小时，选择排序比冒泡排序快。

5.归并排序

归并排序相对来说比较复杂，也没有多研究，就看一下大概的思想和代码。主要的思想是：将序列等分排序，将序列分为两个子序列，再排好两个子序列后将其合并起来。子序列的排序有和主序列类似，也是将其分为两个子序列，...最后将所有序列归并起来即可（也是利用了递归的方法）。主要代码：

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  <span style="font-size:14px;">\#include<stdio.h>  
2.  // 一个递归函数  
3.  void mergesort(int \*num,int start,int end);  
4.  // 这个函数用来将两个排好序的数组进行合并  
5.  void merge(int \*num,int start,int middle,int end);  
6.  int main()\{   
7.      // 测试数组      
8.      int num\[10\]= \{12,54,23,67,86,45,97,32,14,65\};     
9.      int i;  
10.     // 排序之前   
11.     printf("Before sorting:\\n");      
12.     for (i=0; i<10; i++)      
13.     \{         
14.         printf("%3d",num\[i\]);     
15.     \}     
16.     printf("\\n");     
17.     // 进行合并排序     
18.     mergesort(num,0,9);   
19.   
20.     printf("After sorting:\\n");   
21.     // 排序之后   
22.     for (i=0; i<10; i++)      
23.     \{         
24.         printf("%3d",num\[i\]);  
25.     \}     
26.     printf("\\n");     
27.     return 0;  
28. \}  
29. //这个函数用来将问题细分  
30. void mergesort(int \*num,int start,int end)  
31. \{     
32.     int middle;   
33.     if(start<end)     
34.     \{         
35.         middle=(start+end)/2;     
36.         // 归并的基本思想        
37.         // 排左边        
38.         mergesort(num,start,middle);          
39.         // 排右边    
40.         mergesort(num,middle+1,end);          
41.         // 合并     
42.         merge(num,start,middle,end);      
43.     \}  
44. \}  
45. //这个函数用于将两个已排好序的子序列合并  
46. void merge(int \*num,int start,int middle,int end)  
47. \{     
48.     int n1=middle-start+1;    
49.     int n2=end-middle;    
50.     // 动态分配内存，声明两个数组容纳左右两边的数组     
51.     int \*L=new int\[n1+1\];     
52.     int \*R=new int\[n2+1\];     
53.     int i,j=0,k;      
54.     //将新建的两个数组赋值      
55.     for (i=0; i<n1; i++)      
56.     \{         
57.         \*(L+i)=\*(num+start+i);  
58.     \}  
59.     // 哨兵元素     
60.     \*(L+n1)=1000000;      
61.     for (i=0; i<n2; i++)     
62.     \{         
63.         \*(R+i)=\*(num+middle+i+1);     
64.     \}     
65.     \*(R+n2)=1000000;      
66.     i=0;      
67.     // 进行合并   
68.     for (k=start; k<=end; k++)      
69.     \{         
70.         if(L\[i\]<=R\[j\])          
71.         \{             
72.             num\[k\]=L\[i\];              
73.             i++;      
74.         \}         
75.         else          
76.         \{             
77.             num\[k\]=R\[j\];          
78.             j++;          
79.         \}     
80.     \}     
81.     delete \[\] L;      
82.     delete \[\] R;  
83. \}</span>

[view plain]: http://blog.csdn.net/skyandcode/article/details/8607819#

发表评论取消回复

表情：

评论列表（有 0 条评论，102人围观）

还没有评论，来说两句吧...

相关阅读

相关 Redis五种基本类型

目录一、简单介绍 1、string字符串类型 2、hash哈希类型 3、list列表类型 4、set集合类型 5、zset有序集合类型二、命令五种基本类型

青旅半醒/ 2024年03月31日 17:33/ 0 赞/ 40 阅读

相关 JavaScript：五种基本数据类型

JavaScript基本类型;五种如果六种（symbol( )） 1. string : 数据外面有 ‘’ 或者 “” 把类型归类为字符串!; 可以表达任意数据，或者说任何

电玩女神/ 2023年02月18日 08:08/ 0 赞/ 101 阅读

相关 Redis的基本知识（五种基本类型使用）

Redis的基本知识 Redis是单线程 Redis为什么单线程也这么快？五大数据类型 Redis-Key String类型

「爱情、让人受尽委屈。」/ 2022年10月29日 07:38/ 0 赞/ 162 阅读

相关几种基本的排序算法

1.冒泡排序: 冒泡排序的目标就是通过第一次循环将最大(最小)的数找出来,第二次循环将次大(次小)的数找出来...................., 冒泡排序在最坏情况下

约定不等于承诺〃/ 2022年09月25日 00:25/ 0 赞/ 179 阅读

相关五种基本排序

最近在看数据结构，想把几个简单的排序在过一遍，发现还没那么容易，最简单的冒泡排序代码没那么容易敲出来。下面把5种排序复习一下： 1. 冒泡排序：冒泡排序是最简单也是

Love The Way You Lie/ 2022年08月19日 13:11/ 0 赞/ 103 阅读

相关 java 常用五种排序

//冒泡排序 //依次比较相邻的两个元素，通过一次比较把未排序序列中最大（或最小）的元素放置在未排序序列的末尾。 public static void

比眉伴天荒/ 2022年07月28日 01:18/ 0 赞/ 106 阅读

相关 PHP四种基本排序算法

前提：分别用冒泡排序法，快速排序法，选择排序法，插入排序法将下面数组中的值按照从小到大的顺序进行排序。 $arr(1,43,54,62,21,66,32,78,36,76

青旅半醒/ 2022年06月05日 08:15/ 0 赞/ 159 阅读

相关 redis的五种基本类型

redis基本数据类型 redis一共分为5中基本数据类型：String,Hash,List,Set,ZSet 第一种String String类型是包含很多种类

超、凢脫俗/ 2022年05月23日 06:28/ 0 赞/ 149 阅读

相关 Java五种基本注解实战

一点睛 @Override @Deprecated @SuppressWarnings @SafeVarargs @FunctionalInterface 二实

冷不防/ 2021年09月29日 13:28/ 0 赞/ 225 阅读

相关进程五种基本状态

![这里写图片描述][20160906192211991] > 创建状态：进程在创建时需要申请一个空白PCB，向其中填写控制和管理进程的信息，完成资源分配。如果创建工作无法完

末蓝、/ 2021年06月10日 20:41/ 0 赞/ 338 阅读