常见排序算法分析

一.常见排序算法的实现

1.冒泡排序

冒泡排序是非常容易理解和实现,,以从小到大排序举例:

设数组长度为N。

1.比较相邻的前后二个数据,如果前面数据大于后面的数据,就将二个数据交换。

2.这样对数组的第0个数据到N-1个数据进行一次遍历后,最大的一个数据就“沉”到数组第N-1个位置。

3.N=N-1,如果N不为0就重复前面二步,否则排序完成。

按照定义很容易写出代码:

void bubbleSort(int arr[],int n)
{
    int i,j,t;
     for(i=0;i<n-1;i++)
        for(j=0;j<n-i-1;j++)
            if(arr[j+1]<arr[j])
            {
              t=arr[j+1];
              arr[j+1]=arr[j];
              arr[j]=t;
             }
}

 测试代码:

# include <stdio.h>
 
void bubbleSort(int arr[],int n)
{
    int i,j,t;
     for(i=0;i<n-1;i++)
        for(j=0;j<n-i-1;j++)
            if(arr[j+1]<arr[j])
            {
              t=arr[j+1];
              arr[j+1]=arr[j];
              arr[j]=t;
             }
}
 
void print(int arr[],int n)    //打印数组
{
    int i=0;
    for(;i<n;i++)
    {
        printf("%d  ",arr[i]);
    }
    printf("\n");
}
int main(void)
{
    int arr[]={49,15,52,64,98};    //测试数据
    print(arr,5);
    bubbleSort(arr,5);
        printf("排序后的结果:\n");
    print(arr,5);
    return 0;
}

 详细分析:见冒泡排序

2.快速排序

一趟快速排序的算法是:

   1)、设置两个变量I、J,排序开始的时候I:=1,J:=N;

   2)以第一个数组元素作为关键数据,赋值给X,即X:=A[1];

   3)、从J开始向前搜索,即由后开始向前搜索(J:=J-1),找到第一个小于X的值,两者交换;

   4)、从I开始向后搜索,即由前开始向后搜索(I:=I+1),找到第一个大于X的值,两者交换;

   5)、重复第3、4步,直到I=J;

   例如:待排序的数组A的值分别是:(初始关键数据X:=49)

                   A[1]     A[2]     A[3]     A[4]     A[5]      A[6]     A[7]:

49        38       65       97       76       13        27

进行第一次交换后:   27        38       65       97       76       13        49

                   ( 按照算法的第三步从后面开始找

进行第二次交换后:   27        38       49       97       76       13        65

                  ( 按照算法的第四步从前面开始找>X的值,65>49,两者交换,此时I:=3 )

进行第三次交换后:   27        38       13       97       76       49        65

( 按照算法的第五步将又一次执行算法的第三步从后开始找

进行第四次交换后:   27        38       13       49       76       97        65

( 按照算法的第四步从前面开始找大于X的值,97>49,两者交换,此时J:=4 )

      此时再执行第三不的时候就发现I=J,从而结束一躺快速排序,那么经过一躺快速排序之后的结果是:27        38       13       49       76       97        65,即所以大于49的数全部在49的后面,所以小于49的数全部在49的前面。

int quicksort(vector<int> &v, int left, int right){
        if(left < right){
 
                int key = v[left];
                int low = left;
                int high = right;
 
                while(low < high){
                        while(low < high && v[high] > key){
                                high--;
                        }
 
                        v[low] = v[high];
 
                        while(low < high && v[low] < key){
                                low++;
                        }
 
                        v[high] = v[low]
 
                }
 
                v[low] = key;
                quicksort(v,left,low-1);
                quicksort(v,low+1,right);
 
        }
}

  详细分析:见快速排序

3.直接插入排序

直接插入排序(straight insertion sort)的作法是:

     每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。

  • 第一趟比较前两个数,然后把第二个数按大小插入到有序表中;
  • 第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;
  • 依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。

代码实现:

void InsertSortArray()
{
    for(int i=1;i<n;i++)//循环从第二个数组元素开始,因为arr[0]作为最初已排序部分
    {
        int temp=arr[i];//temp标记为未排序第一个元素
        int j=i-1;
        while (j>=0 && arr[j]>temp)/*将temp与已排序元素从大到小比较,寻找temp应插入的位置*/
        {
            arr[j+1]=arr[j]; 
            j--;
        }
        arr[j+1]=temp;
    }
} 

详细分析见直接插入排序

4.选择排序

思想:首先设置一个变量保存元素下标,将该元素与其他元素进行比较。若大于其他元素则变换其下标,比较完后再判断其下标是否发生变化,若变化则交换两个元素的值,否则不变。经过一次比较,即可得出数列中的最小元素并将其放在数列的首位。一次类推,经过n-1次比较即可得到n个元素从小到大的排列。

int i , temp;
for(i = 0 ; i < 8 ; ++i)
	scanf("%d" , &x[i]);
for(i = 0 ; i < 7 ; ++i)
{
	k = i;
	for(j = i + 1 ; j < 8 ; ++j)
		if(x[i] > x[j])
			k = j;
	if(k != i)
	{
		temp = x[k];
		x[k] = x[i];
		x[i] = temp;
	}
}

二.其他算法的分析

1 快速排序(QuickSort) 快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。快速排序可以由下面四步组成。 (1) 如果不多于1个数据,直接返回。 (2) 一般选择序列最左边的值作为支点数据。 (3) 将序列分成2部分,一部分都大于支点数据,另外一部分都小于支点数据。 (4) 对两边利用递归排序数列。 快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法,但是就通常情况而言,没有比它更快的了。快速排序是递归的,对于内存非常有限的机器来说,它不是一个好的选择。 2 归并排序(MergeSort) 归并排序先分解要排序的序列,从1分成2,2分成4,依次分解,当分解到只有1个一组的时候,就可以排序这些分组,然后依次合并回原来的序列中,这样就可以排序所有数据。合并排序比堆排序稍微快一点,但是需要比堆排序多一倍的内存空间,因为它需要一个额外的数组。 3 堆排序(HeapSort) 堆排序适合于数据量非常大的场合(百万数据)。 堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录,因为快速排序,归并排序都使用递归来设计算法,在数据量非常大的时候,可能会发生堆栈溢出错误。 堆排序会将所有的数据建成一个堆,最大的数据在堆顶,然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆,交换数据,依次下去,就可以排序所有的数据。 4 Shell排序(ShellSort) Shell排序通过将数据分成不同的组,先对每一组进行排序,然后再对所有的元素进行一次插入排序,以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。 Shell排序比冒泡排序快5倍,比插入排序大致快2倍。Shell排序比起QuickSort,MergeSort,HeapSort慢很多。但是它相对比较简单,它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。 5 插入排序(InsertSort) 插入排序通过把序列中的值插入一个已经排序好的序列中,直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序,或者重复排序超过200数据项的序列。 6 冒泡排序(BubbleSort) 冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素,使较大的数据下沉,较小的数据上升。它是O(n^2)的算法。 7 交换排序(ExchangeSort)和选择排序(SelectSort) 这两种排序方法都是交换方法的排序算法,效率都是 O(n2)。在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段,在实际中使用较少。 8 基数排序(RadixSort) 基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法,但是它只能用于 整数的排序,如果我们要把同样的办法运用到浮点数上,我们必须了解浮点数的存储格式,并通过特殊的方式将浮点数映射到整数上,然后再映射回去,这是非常麻 烦的事情,因此,它的使用同样也不多。而且,最重要的是,这样算法也需要较多的存储空间。 9 总结 下面是一个总的表格,大致总结了我们常见的所有的排序算法的特点。

image.png

排序法

平均时间

最差情形

稳定度

额外空间

备注

冒泡

O(n2)

O(n2)

稳定

O(1)

n小时较好

交换

O(n2)

O(n2)

不稳定

O(1)

n小时较好

选择

O(n2)

O(n2)

不稳定

O(1)

n小时较好

插入

O(n2)

O(n2)

稳定

O(1)

大部分已排序时较好

基数

O(logRB)

O(logRB)

稳定

O(n)

B是真数(0-9),R是基数(个十百)

Shell

O(nlogn)

O(ns) 1<s<2

不稳定

O(1)

s是所选分组

快速

O(nlogn)

O(n2)

不稳定

O(nlogn)

n大时较好

归并

O(nlogn)

O(nlogn)

稳定

O(1)

n大时较好

O(nlogn)

O(nlogn)

不稳定

O(1)

n大时较好

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏闰土大叔

闰土说JS进阶之「戏说数组」

前言 最近一段时间,我女票跟我诉苦说他们公司很多同事(包括老板),一到中午都痴迷于玩王者荣耀,不玩的会受到排挤,参与不进话题。“什么?你居然不知道梦奇,这可是王...

386110
来自专栏编程

Python函数之一切皆对象

今天我们要讲的是 对象 避免误会,常老师先澄清一下,这里面说的对象指的是object,不是你的lover,也不是你的sweetheart…… 有的小伙伴可能会觉...

20570
来自专栏趣谈编程

直接插入排序

登鹳雀楼 唐·王之涣 白日依山尽,黄河入海流。  欲穷千里目,更上一层楼。 面试官:聊聊插入排序 插入排序是一种比较简单直观的排序算法,适用处理数据量比...

41650
来自专栏java一日一条

面试中的 10 大排序算法总结

查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗,只...

22330
来自专栏怀英的自我修炼

Java漫谈6

今天这篇想聊聊数组。 在聊数组之前先聊个别的,如果想在Java中实现一个 数字-月份 转换,那我该怎么做呢?就比如数字1代表了一月份,数字2代表了二月份…数字1...

37290
来自专栏我的博客

冒泡排序

原理: 1、比较相邻的元素。如果第一个比第二个大(小),就交换他们两个。 2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元...

32550
来自专栏机器学习算法与Python学习

“基数排序”展现Python的优雅与简洁

在这儿那桶排序为例目的不是向大家介绍基数排序这种排序方式,是想通过基数排序的实现来展现Python的简洁与优雅。在这儿先简单的介绍一下基数排序,至于具体的内容会...

37650
来自专栏编程

这是新手自学编程的开始,程序员入门的诀窍

虽然学习IT编程技术已经是越来越热了,但是如果作为一个新手程序员想要入门还是很困难的,这里有一些前端程序员总结的程序员入门的好技巧。相对java,C,Pytho...

31370
来自专栏前端正义联盟

我来重新学习 javascript 的面向对象(part 5)

这是最后的最后了,我会顺便总结一下各种继承方式的学习和理解。(老板要求什么的,管他呢)

9710
来自专栏菜鸟前端工程师

JavaScript学习笔记006-作用域0类型转换

10520

扫码关注云+社区

领取腾讯云代金券