数组的几种排序算法的实现

ゝ一纸荒年。 2022-05-19 13:19 213阅读 0赞

数据结构中的排序算法,各有用处,比如:   
1,直接插入排序,在序列基本有序的情况下,移动的次数比较少,但是比较次数是一样的   
复杂度O(n\*n);   
2,冒泡排序,这个不用说了吧,刚学C的人都懂了   
3,希尔排序,只要是找出较好的增量,将数据排列成基本有序时,最后一次来一次直接插入排序,是对直接插入排序的改进.复杂度为O(n(3/2));   
4,快速排序,算是所有排序中复杂度一般情况下比较好的算法,它设了一个枢轴,将它分为两部分,左边比它小,右边的比它大,复杂度为O(nlog n);   
5,选择排序,和冒泡差不多的复杂度,   
6,归并排序,这是一种稳定的排序方法,将数据分为各个有序的部分,再组合为一个整体,只要用递归的方法.   
7,还有基数排序,树形排序,堆排序,等等,这里不多说了,你多多学习多多消化吧,慢慢学吧,多看看课本的算法,自己实现一次,学完了你的编程能力就能很好的提高了.

解释：时间复杂度

举个简单的例子，要从0加到n，我们会这么写：  
int sum = 0;  
for(int i = 0; i<=n; ++i)  
\{  
   sum += i;  
\}  
一共算了n次加法，那么就说这个时间复杂度是O(n)。当然O(n)的精确的概念是，是n的最高次方，比如，某个计算共计算了3n + 2次，那么这个时间复杂度也是O(n)，因为3n + 2中的最高次方是n。  
  
如果代码这么写：  
int sum = 0;  
for(int i = 0; i<=n; ++i)  
\{  
   for(int j = 0; j <=n; ++j)  
   \{  
      sum += (i + j);  
   \}  
\}  
  
很显然一共算了n^2次加法，那么就说这个时间复杂度是O(n^2)，和上面类似，如果某个算法计算了3\*n^2 + n + 1次，其时间复杂度仍然是O(n^2)，因为3\*n^2 + n + 1中最高的次方是n^2  
  
所谓O(1)就是计算的次数是个常量，我们还以上面从0加到n的例子来说，如果我们用等差数列的公式，那么，代码可以这么写：  
int sum = n \* (n + 1) / 2  
不管n有多大(当然不能溢出了)，通过上面的公式只需计算一次，也就说计算的次数是不变的，这种情况的时间复杂度就可以说成O(1)。 再比如如果某个计算，不管其他条件怎么变化，均只需计算5次即可得出结果，那么这种情况的时间复杂度，也是O(1)。

数组的排序方法有很多，效率也各不相同，下面简单介绍一下几种常见的排序算法。

1.选择排序法：将要排序的数组分成两部分，一部分是从大到小已经排好序的，一部分是无序的，从无序的部分取出最小的放到已经排序的最后面。实现如下：

**\[java\]** [view plain][][copy][view plain]

1.  public int\[\] choiceSort(int\[\] arr)\{  
2.          for(int i = 0;i < arr.length;i++)\{  
3.              int m = i;  
4.              for(int j = i + 1;j < arr.length;j++)\{  
5.                  //如果第j个元素比第m个元素小，将j赋值给m  
6.                  if(arr\[j\] < arr\[m\])\{  
7.                      m = j;  
8.                  \}  
9.              \}  
10.             //交换m和i两个元素的位置  
11.             if(i != m)\{  
12.                 int t = arr\[i\];  
13.                 arr\[i\] = arr\[m\];  
14.                 arr\[m\] = t;  
15.             \}  
16.         \}  
17.         return arr;  
18.     \}

2.冒泡排序法：冒泡排序的思路就不用介绍了。上实现：

**\[java\]** [view plain][][copy][view plain]

1.  public int\[\] bubbleSort(int\[\] arr)\{  
2.          for(int i = 0;i < arr.length;i++)\{  
3.              //比较两个相邻的元素  
4.              for(int j = 0;j < arr.length-i-1;j++)\{  
5.                  if(arr\[j\] > arr\[j+1\])\{  
6.                      int t = arr\[j\];  
7.                      arr\[j\] = arr\[j+1\];  
8.                      arr\[j+1\] = t;  
9.                  \}  
10.             \}  
11.         \}  
12.         return arr;  
13.     \}

3.插入排序法：将要排序的数组分成两部分，每次从后面的部分取出索引最小的元素插入到前一部分的适当位置。基本实现如下：

**\[java\]** [view plain][][copy][view plain]

1.  public int\[\] insertSort(int\[\] arr)\{  
2.          for(int i = 1;i < arr.length;i++)\{  
3.              int temp = arr\[i\];  
4.              int j = i - 1;  
5.              while(temp < arr\[j\])\{  
6.                  arr\[j+1\] = arr\[j\];  
7.                  j--;  
8.                  if(j == -1)\{  
9.                      break;  
10.                 \}  
11.             \}  
12.             arr\[j+1\] = temp;  
13.         \}  
14.         return arr;  
15.     \}

4.快速排序法：快速排序法号称是目前最优秀的算法之一，实现思路是，将一个数组的排序问题看成是两个小数组的排序问题，而每个小的数组又可以继续看成更小的两个数组，一直递归下去，直到数组长度大小最大为2。实现如下：

**\[java\]** [view plain][][copy][view plain]

1.  public int\[\] fastSort(int\[\] arr,int left,int right)\{  
2.          if(left < right)\{  
3.              int s = arr\[left\];  
4.              int i = left;  
5.              int j = right + 1;  
6.              while(true)\{  
7.                  //向右找大于s的元素的索引  
8.                  while(i+1 < arr.length && arr\[++i\] < s);  
9.                  //向左找小于s的元素的索引  
10.                 while(j-1 > -1 && arr\[--j\] > s);  
11.                 //如果i >= j 推出循环  
12.                 if(i >= j)\{  
13.                     break;  
14.                 \}else\{  
15.                     //教化i和j位置的元素  
16.                     int t = arr\[i\];  
17.                     arr\[i\] = arr\[j\];  
18.                     arr\[j\] = t;  
19.                 \}  
20.             \}  
21.             arr\[left\] = arr\[j\];  
22.             arr\[j\] = s;  
23.             //对左面进行递归  
24.             fastSort(arr,left,j-1);  
25.             //对右面进行递归  
26.             fastSort(arr,j+1,right);  
27.         \}  
28.         return arr;  
29.     \}

5.希尔排序（Shell Sort）又称为缩小增量排序，输入插入排序算法，是对直接排序算法的一种改进。本文介绍希尔排序算法。

对于插入排序算法来说，如果原来的数据就是有序的，那么数据就不需要移动，而插入排序算法的效率主要消耗在数据的移动中。因此可知：如果数据的本身就是有序的或者本身基本有序，那么效率就会得到提高。

希尔排序的基本思想是：将需要排序的序列划分成为若干个较小的子序列，对子序列进行插入排序，通过则插入排序能够使得原来序列成为基本有序。这样通过对较小的序列进行插入排序，然后对基本有序的数列进行插入排序，能够提高插入排序算法的效率。

在希尔排序中首先解决的是子序列的选择问题。对于子序列的构成不是简单的分段，而是采取相隔某个增量的数据组成一个序列。一般的选择原则是：去上一个增量的一般作为此次序列的划分增量。首次选择序列长度的一般为增量。

先假如：数组的长度为10，数组元素为：25,19,6,58,34,10,7,98,160,0

整个希尔排序的算法过程如下如所示：

![79ab1624f331df484d088dea.jpg][]

上图是原始数据和第一次选择的增量 d = 5。本次排序的结果如下图：

![eb2a341386ff7f6adc5401f5.jpg][]

上图是第一次排序的结果，本次选择增量为 d=2。 本次排序的结果如下图：

![f3512ec84e2bbf5e7e3e6ff7.jpg][]

当d=1 是进行最后一次排序，本次排序相当于冒泡排序的某一次循环。最终结果如下：

![cdfffc4f5d40817faec3abf2.jpg][]

在实际使用过程中，带排序的数据肯定不是只有十个，但是上述是希尔排序的思想。其实希尔排序只是插入排序的一种优化。

希尔排序的整个流程如下图所示：假设带排序的数据结构为整型数组 A\[n\] 数组长度为 n

C++实现希尔排序的代码如下所示：

// ShellSort.cpp : Defines the entry point for the console application.

\#include "stdafx.h"

\#include <iostream>

using namespace std;

void Display(int array\[\],int length);

void ShellSort(int array\[\],int length);

int main(int argc, char\* argv\[\])

int arr\[10\] = \{25,19,6,58,34,10,7,98,160,0\};

Display(arr,10);

ShellSort(arr,10);

Display(arr,10);

system("pause");

return 0;

//输出数组

void Display(int array\[\],int length)

for(int i =0;i<length;i++)

cout<<array\[i\]<<", ";

cout<<endl;

//希尔排序算法的实现

void ShellSort(int array\[\],int length)

int d = length/2;   //设置希尔排序的增量

int i ;

int j;

int temp;

while(d>=1)

for(i=d;i<length;i++)

temp=array\[i\];

j=i-d;

while(j>=0 && array\[j\]>temp)

array\[j+d\]=array\[j\];

j=j-d;

array\[j+d\] = temp;

Display(array,10);

d= d/2;    //缩小增量

/\*

希尔排序是对插入排序的一种改进。该算法思路和代码都比较复杂。以上代码在VC 6.0 中成功运行

\*/

![3d2e36ea9270409ad439c9c0.jpg][]

[view plain]: http://blog.csdn.net/letthinking/article/details/6764996
[79ab1624f331df484d088dea.jpg]: /images/20220519/ae708d622e8e44db8ae5071d3eac9391.png
[eb2a341386ff7f6adc5401f5.jpg]: /images/20220519/d669df142b2d4729a43fe390d1bfd430.png
[f3512ec84e2bbf5e7e3e6ff7.jpg]: /images/20220519/0c5793bd82b6475d810ffc4f05a22713.png
[cdfffc4f5d40817faec3abf2.jpg]: /images/20220519/d110547740484b04972e4813c61778d2.png
[3d2e36ea9270409ad439c9c0.jpg]: /images/20220519/b0a303cb42914d2d869f1b81f9686de6.png