精华内容
下载资源
问答
  • 常用几种排序算法

    千次阅读 2018-05-01 11:18:48
    时间复杂度为O(n2)的排序算法 插入排序 插入排序的主要思想是:每一次得到一个新的元素,就和原来已经排序好的序列对比,然后将这个新的元素插入到正确的位置,具体的代码实现:void insertSort(int a[],int ...

    三种时间复杂度为O(n2)的排序算法

        插入排序

        插入排序的主要思想是:每一次得到一个新的元素,就和原来已经排序好的序列对比,然后将这个新的元素插入到正确的位置,具体的代码实现:

    void insertSort(int a[],int length)
    {
    	if(a==NULL||length<=0) return;
    	for(int i=1;i<length;i++)
    	{
    		int j=i;
    		while(j-1>=0&&a[j-1]>a[j])
    		{
    			int tmp=a[j-1];
    			a[j-1]=a[j];
    			a[j]=tmp;
    			j--;
    		}
    	}
    
    }
    
    

        插入排序的最差情况,这里做的是从小到大的排列,假设对于第k次循环,需要比较的k前的元素和第k个的大小,需要将第k个元素移动到小于等于的位置,所有对于最差的情况,应该是该数组逆序排列,从第i(i>=1)个元素开始,每一个元素,要移动i位,最差的时间复杂度应该是1+2+3+....+n-1 ,所以应该是O(n2).

        最好的时间复杂读,是已经排好序,也就是只需要遍历一遍,时间复杂度为O(n);

        同样的道理,平均情况应该也是O(n2).

        冒泡排序

        冒泡排序的主要思想是,小的下沉,大的上浮。

        代码实现如下:

    void bubSort(int a[],int length)
    {
    	if(a==NULL||length<=0) return;
    	for(int i=1;i<length;i++)
    	{
    		for(int j=i;j>0;j--)
    		{
    			if(a[j]<a[j-1])
    			{
    				int tmp=a[j];
    				a[j]=a[j-1];
    				a[j-1]=tmp;
    			}
    		}
    	}
    }

        通过代码可以看出,冒泡排序的时间复杂度为O(n2)

    选择排序

        主要的思想是:从数组中选择一个最小的,放在最前的位置,然后选择次小的,依次下去,这样就形成了一个有序的数组。

        代码实现:

    void selectSort(int a[],int length)
    {
    	if(a==NULL||length<=0) return;
    	for(int i=0;i<length;i++)
    	{
    		int min=a[i];
    		int pos=i;
    		for(int j=i+1;j<length;j++)
    		{
    			if(a[j]<min)
    			{
    				min=a[j];
    				pos=j;
    			}
    		}		
    		//交换最小的
    		int tmp=a[i];
    		a[i]=min;
    		a[pos]=tmp;
    	}
    }
    

        可以看出,,选择排序最好、最差、平均都是O(n2);

    一下是三种简单排序算法的比较

        Shell排序

            主要的思想:Shell排序是插入排序的改进,由于插入排序是相邻元素之间的比较,Shell排序主要的是将比较的元素进行非增量比较,也就是将元素进行分为多个序列,然后进行比较,但是要注意的是,在最后,还要进行一次增量为1的比较,也就是常规的插入排序。

            代码实现

    void shellInsertSort(int a[],int length,int incr)
    {
    	for(int i=incr;i<length;i+=incr)
    	{
    		int j=i;
    		while(j-incr>=0&&a[j-incr]>a[j])
    		{
    			int tmp=a[j-1];
    			a[j-1]=a[j];
    			a[j]=tmp;
    			j-=incr;
    		}
    	}
    }
    
    void shellSort(int a[],int length)
    {
    	for(int i=length;i>2;i=i/2)
    		for(int j=0;j<i;j++)
    			shellInsertSort(a,length-j,i);
    	shellInsertSort(a,length,1);
    }

        Shell排序的最好、最坏时间复杂度为O(n2),平均时间复杂为O(n1.5)

    快速排序

        快速排序的主要思想:主要是利用分治的思想,将数组分为两部分,左边的部门小于a[k],右边的元素大于等于a[k-1],然后重复以上步骤。

        代码实现:

    public class QuickSort {
    
        public static void quickSort(int arr[],int _left,int _right){
            int left = _left;
            int right = _right;
            int temp = 0;
            if(left <= right){   //待排序的元素至少有两个的情况
                temp = arr[left];  //待排序的第一个元素作为基准元素
                while(left != right){   //从左右两边交替扫描,直到left = right
    
                    while(right > left && arr[right] >= temp)  
                         right --;        //从右往左扫描,找到第一个比基准元素小的元素
                      arr[left] = arr[right];  //找到这种元素arr[right]后与arr[left]交换
    
                    while(left < right && arr[left] <= temp)
                         left ++;         //从左往右扫描,找到第一个比基准元素大的元素
                      arr[right] = arr[left];  //找到这种元素arr[left]后,与arr[right]交换
    
                }
                arr[right] = temp;    //基准元素归位
                quickSort(arr,_left,left-1);  //对基准元素左边的元素进行递归排序
                quickSort(arr, right+1,_right);  //对基准元素右边的进行递归排序
            }        
        }
        public static void main(String[] args) {
            int array[] = {10,5,3,1,7,2,8};
            System.out.println("排序之前:");
            for(int element : array){
                System.out.print(element+" ");
            }
            
            quickSort(array,0,array.length-1);
    
            System.out.println("\n排序之后:");
            for(int element : array){
                System.out.print(element+" ");
            }
    
        }
    
    }

        快速排序的最好和平均时间O(nlogN),最差情况是O(n2).

    堆排序

        主要的思想:利用堆的性质。

        堆排序在上几节中已经实现,这里只是讲解最坏、最差、平均的时间复杂度为O(nlogN);

    归并排序

    void mergeSort(int a[],int tmp[],int left,int right)
    {
    	int mid=(left+right)/2;
    	if(left==right) return;
    	mergeSort(a,tmp,left,mid);
    	mergeSort(a,tmp,mid,right);
    	for(int i=left;i<=right;i++)
    	{
    		tmp[i]=a[i];
    	}
    	int i1=left,j=mid+1;
    	for(int i=left;i<=right;i++)
    	{
    		if(i1==mid+1){
    			//这里左边的数组使用完毕
    			a[i]=tmp[j++];
    		}
    		else if(j>right)
    		{
    			a[i]=tmp[i1++];
    		} 
    		else if(a[i1]<a[j])
    		{
    			a[i]=a[i1++];
    		}
    		else
    		{
    			a[i]=a[j++];
    		}
    	}
    }
    
        对于归并排序,划分的深度为logN,无论好坏,平均,这个算法的平均复杂度为(nlongN)



    展开全文
  • 常用排序算法的时间复杂度和空间复杂度 排序法  最差时间分析 平均时间复杂度  稳定度  空间复杂度  冒泡排序 O(n2) O(n2)  稳定  O(1)  ...
    

    常用的排序算法的时间复杂度和空间复杂度

    排序法 

    最差时间分析

    平均时间复杂度 

    稳定度 

    空间复杂度 

    冒泡排序

    O(n2)

    O(n2

    稳定 

    O(1) 

    快速排序

    O(n2)

    O(n*log2n) 

    不稳定 

    O(log2n)~O(n) 

    选择排序

    O(n2)

    O(n2

    稳定 

    O(1) 

    二叉树排序

    O(n2)

    O(n*log2n) 

    不一顶 

    O(n) 

    插入排序 

    O(n2)

    O(n2

    稳定 

    O(1) 

    堆排序

    O(n*log2n) 

    O(n*log2n) 

    不稳定 

    O(1) 

    希尔排序

    O

    不稳定 

    O(1)


    1、时间复杂度
    1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)
    2)时间复杂度 在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,Tn)/f(n)的极限值为不等于零的常数,则称f(n)T(n)的同数量级函数。记作T(n)=(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
    在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。 按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。 2、空间复杂度 与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n)) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似,不再赘述。
    3)渐进时间复杂度评价算法时间性能   主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。

    2、类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。
    空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是就地/"进行的,是节省存储的算法,如这一节介绍过的几个算法都是如此;有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。

    当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1)当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为0(10g2n);当一个算法的空I司复杂度与n成线性比例关系时,可表示为0(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。

    展开全文
  • 常见几种java排序算法

    万次阅读 多人点赞 2019-02-18 18:08:16
    1.插入排序 public class InsertSort { public static void sort(int[] arr) { if (arr.length &amp;amp;amp;gt;= 2) { for (int i = 1; i &amp;amp;amp;lt; arr.length; i++) { //挖出一个要用来插入...

    1.插入排序

    这个打麻将或者打扑克的很好理解, 比如有左手有一副牌1,2,4,7 ,来一张3的牌, 是不是就是手拿着这张牌从右往左插到2,4之间

    一次插入排序的操作过程:
    将待插元素,依次与已排序好的子数列元素从后到前进行比较,如果当前元素值比待插元素值大,则将移位到与其相邻的后一个位置,否则直接将待插元素插入当前元素相邻的后一位置,因为说明已经找到插入点的最终位置
    在这里插入图片描述

    public class InsertSort {
    
        public static void sort(int[] arr) {
            if (arr.length >= 2) {
                for (int i = 1; i < arr.length; i++) {
                    //挖出一个要用来插入的值,同时位置上留下一个可以存新的值的坑
                    int x = arr[i];
                    int j = i - 1;
                    //在前面有一个或连续多个值比x大的时候,一直循环往前面找,将x插入到这串值前面
                    while (j >= 0 && arr[j] > x) {
                        //当arr[j]比x大的时候,将j向后移一位,正好填到坑中
                        arr[j + 1] = arr[j];
                        j--;
                    }
                    //将x插入到最前面
                    arr[j + 1] = x;
                }
            }
        }
    }
    

    2.分治排序法,快速排序法

    简单的说, 就是设置一个标准值, 将于这个值的放到右边(不管排序), 将于这个值的放到左边(不管排序), 那么这样只是区分了左小右大, 没有排序, 没关系, 左右两边再重复这个步骤.直到不能分了为止.
    详细说就是:

    1. 选择待排数列的首部第一个元素为基准元素x,设置两指针,分别指向数列首尾部位置,假设两指针分别设为ij
    2. 每次遍历的过程是这样的,首先从右到左遍历指针j所指向的元素,直到j指向的元素值小于基准元素x时,停止遍历,将其放到i的位置(因为i的值已经拷贝成了基准x腾出了位置)
    3. i往右挪一步, i++,接着轮到指针i左到右遍历,直到i所指向的元素值大于基准元素x时,停止遍历,将其放到j的位置(因为上面一步j的值已经占用到了i的位置,腾出位置了)
    4. 依此类推,两边轮流遍历, 直到指针i与指针j相等或者大于(实际肯定是i==j)时,停止外部循环。此时必定左边都是比x小的, 右边是比x大的.
    5. 最后直接将基准元素x直接放置于指针i所指向的位置即可
    6. 完成分区操作, 从i的位置一分为二, 左边和右边再递归执行上面的操作. 层层细分

    接下来,我们通过示图来展示上述分区算法思路的过程:
    在这里插入图片描述

    public class QuickSort {
    
        public static void sort(int[] arr,int begin,int end) {
            //先定义两个参数接收排序起始值和结束值
            int a = begin;
            int b = end;
            //先判断a是否大于b
    
            if (a >= b) {
                //没必要排序
                return;
            }
            //基准数,默认设置为第一个值
            int x = arr[a];
    
            //循环
            while (a < b) {
                //从后往前找,找到一个比基准数x小的值,赋给arr[a]
                //如果a和b的逻辑正确--a<b ,并且最后一个值arr[b]>x,就一直往下找,直到找到后面的值大于x
                while (a < b && arr[b] >= x) {
                    b--;
                }
                //跳出循环,两种情况,一是a和b的逻辑不对了,a>=b,这时候排序结束.二是在后面找到了比x小的值
                if (a < b) {
                    //将这时候找到的arr[b]放到最前面arr[a]
                    arr[a] = arr[b];
                    //排序的起始位置后移一位
                    a++;
                }
    
                //从前往后找,找到一个比基准数x大的值,放在最后面arr[b]
                while (a < b && arr[a] <= x) {
                    a++;
                }
                if (a < b) {
                    arr[b] = arr[a];
                    //排序的终止位置前移一位
                    b--;
                }
            }
            //跳出循环 a < b的逻辑不成立了,a==b重合了,此时将x赋值回去arr[a]
            arr[a] = x;
            //调用递归函数,再细分再排序
            sort(arr,begin,a-1);
            sort(arr,a+1,end);
        }
    }
    

    3.冒泡排序 low版

    每次冒泡过程都是从数列的第一个元素开始,然后依次和剩余的元素进行比较, 跟列队一样, 从左到右两两相邻的元素比大小, 高的就和低的换一下位置. 最后最高(值最大)的肯定就排到后面了.

    但是这只是把最高的排到后面了, 还得找出第二高的, 于是又从第一个开始两两比较, 高的往后站, 然后第二高的也到后面了.

    然后是第三高的再往后排…
    在这里插入图片描述

    public class MaoPao {
    
        public static void  sort(int[] arr){
            for (int i = 1; i < arr.length; i++) {  //第一层for循环,用来控制冒泡的次数
                for (int j = 0; j < arr.length-1; j++) { //第二层for循环,用来控制冒泡一层层到最后
                    //如果前一个数比后一个数大,两者调换 ,意味着泡泡向上走了一层
                    if (arr[j] > arr[j+1] ){
                        int temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                    }
                }
            }
        }
    }
    
    

    4.冒泡排序 bigger版

    补充, 改进后,看下文的测试结果发现提升并不大, 这是正常的, 因为改进后省略的是排序成功后的判断步骤, 而就算没改进, 排序成功后也只不过是对数组进行遍历而已, 没有进行数据更新操作, 而我们知道数组是读取快更新慢的, 所以和上面的版本相比看起来提升不算大

    在这个版本中,改动了两点

    1. 第一点是加入了一个布尔值,判断第二层循环中的调换有没有执行,如果没有进行两两调换,说明后面都已经排好序了,已经不需要再循环了,直接跳出循环,排序结束.
    2. 第二点是第二层循环不再循环到arr.length - 1,因为外面的i循环递增一次,说明数组最后就多了一个排好序的大泡泡.第二层循环也就不需要到最末尾一位了,可以提前结束循环
     /**
     * 终极版冒泡排序
     * 加入一个布尔变量,如果内循环没有交换值,说明已经排序完成,提前终止
     * @param arr
     */
    public static void sortPlus(int[] arr){
        if(arr != null && arr.length > 1){
            for(int i = 0; i < arr.length - 1; i++){
                // 初始化一个布尔值
                boolean flag = true;
                for(int j = 0; j < arr.length - i - 1 ; j++){
                    if(arr[j] > arr[j+1]){
                        // 调换
                        int temp;
                        temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                        // 改变flag
                        flag = false;
                    }
                }
                if(flag){
                    break;
                }
            }
        }
    }
    
    

    5.选择排序

    选择排序也是一种简单直观的排序算法,实现原理比较直观易懂:
    首先在未排序数列中找到最小元素,然后将其与数列的首部元素进行交换,然后,在剩余未排序元素中继续找出最小元素,将其与已排序数列的末尾位置元素交换。以此类推,直至所有元素圴排序完毕.

    同理,可以类比与打扑克和打麻将, 和上面插入排序不同, 插入排序相当于抽一张牌整理好了再抽一张, 而选择排序相当于一次性给你一副乱牌, 然后慢慢整理的感觉.
    这也容易理解为什么选择排序为啥比插入排序慢了. 插入排序是摸一张牌, 然后直接插入到手中已经排好序的牌,再摸下一张牌.
    选择排序相当于在一堆牌中, 不断的找到最小的牌往前面放.

    在这里插入图片描述

    public static void sort(int[] arr){
        for(int i = 0; i < arr.length - 1 ; i++){
            int min = i; // 遍历的区间最小的值
            for (int j = i + 1; j < arr.length ;j++){
                 if(arr[j] < arr[min]){
                     // 找到当前遍历区间最小的值的索引
                     min = j;
                 }
            }
            if(min != i){
                // 发生了调换
                int temp =  arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
            }
        }
    }
    

    6. 归并排序

    归并排序,简单的说把一串数,从中平等分为两份,再把两份再细分,直到不能细分为止,这就是分而治之的分的步骤. 再从最小的单元,两两合并,合并的规则是将其按从小到大的顺序放到一个临时数组中,再把这个临时数组替换原数组相应位置,这就是治. 图解如下:

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    代码:

    public static void mergeSort(int[] a,int s,int e){
        int m = (s + e) / 2;
        if (s < e){
          mergeSort(a,s,m);
          mergeSort(a,m+1,e);
          //归并
          merge(a,s,m,e);
        }
      }
    
      private static void merge(int[] a, int s, int m, int e) {
        //初始化一个从起始s到终止e的一个数组
        int[] temp = new int[(e - s) + 1];
        //左起始指针
        int l = s;
        //右起始指针
        int r = m+1;
        int i = 0;
        //将s-e这段数据在逻辑上一分为二,l-m为一个左边的数组,r-e为一个右边的数组,两边都是有序的
        //从两边的第一个指针开始遍历,将其中小的那个值放在temp数组中
        while (l <= m && r <= e){
          if (a[l] < a[r]){
            temp[i++] = a[l++];
          }else{
            temp[i++] = a[r++];
          }
        }
    
        //将两个数组剩余的数放到temp中
        while (l <= m){
          temp[i++] = a[l++];
        }
        while (r <= e){
          temp[i++] = a[r++];
        }
        
        //将temp数组覆盖原数组
        for (int n = 0; n < temp.length; n++) {
          a[s+n] = temp[n];
        }
        
      }
    

    7. 其他排序

    比如Arrays工具类提供的排序方法。它内部实现也是快速排序

    private static void arraysSort(int[] a){
        Arrays.sort(a);
      }
    

    还有就是将数组转为list,使用集合的排序方法,但是这无异于兜圈子,因为集合底层也是数组

    private static void listSort(int[] a){
        List<Integer> integers = Ints.asList(a);
        Collections.sort(integers);
        integers.toArray(new Integer[a.length]);
      }
    

    7. 比较

    试了一下几个排序的速度,代码如下:

    public static void main(String[] args) {
    
        int[] arr = new int[200000];
        int[] a =getRandomArr(arr);
        int[] b = a.clone();
        int[] c = b.clone();
        int[] d = b.clone();
        int[] e = b.clone();
        int[] f = b.clone();
        int[] g = b.clone();
        int[] h = b.clone();
    
        long s = Clock.systemDefaultZone().millis();
        quickSort(a, 0, a.length - 1);
        System.out.println("quickSort耗时: " + (Clock.systemDefaultZone().millis() - s) + " ms");
    
        s = Clock.systemDefaultZone().millis();
        mergeSort(b,0,b.length-1);
        System.out.println("mergeSort: " + (Clock.systemDefaultZone().millis() - s) + " ms");
    
        s = Clock.systemDefaultZone().millis();
        listSort(c);
        System.out.println("listSort耗时: " + (Clock.systemDefaultZone().millis() - s) + " ms");
    
        s = Clock.systemDefaultZone().millis();
        arraysSort(d);
        System.out.println("arraysSort耗时: " + (Clock.systemDefaultZone().millis() - s) + " ms");
    
        s = Clock.systemDefaultZone().millis();
        maoPaoSort(e);
        System.out.println("maoPaoSort耗时: " + (Clock.systemDefaultZone().millis() - s) + " ms");
    
        s = Clock.systemDefaultZone().millis();
        maoPaoSortPlus(f);
        System.out.println("maoPaoSortPlus耗时: " + (Clock.systemDefaultZone().millis() - s) + " ms");
    
        s = Clock.systemDefaultZone().millis();
        insertSort(g);
        System.out.println("insertSort耗时: " + (Clock.systemDefaultZone().millis() - s) + " ms");
    
        s = Clock.systemDefaultZone().millis();
        selectSort(h);
        System.out.println("selectSort耗时: " + (Clock.systemDefaultZone().millis() - s) + " ms");
    
    
    
    }
    
    /**
       * 获取一个打乱的数组
       * @param arr
       */
      private static int[] getRandomArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
          arr[i] = new Random().nextInt(arr.length);
        }
        return arr;
      }
    

    分别对1k,1w,10w,20w大小的随机数组排序,结果如下:
    得到综合结果是:
    速度: 快速排序>>归并排序>>>>>插入排序>>选择排序>>冒泡排序
    并且可以看到,选择排序,冒泡排序在数据量越来越大的情况下,耗时已经呈指数型上涨,而不是倍数上涨,在50w的时候已经需要足足5分钟以上

    //---1k---
    quickSort耗时: 0 ms
    mergeSort: 1 ms
    listSort耗时: 7 ms
    arraysSort耗时: 1 ms
    maoPaoSort耗时: 3 ms
    maoPaoSortPlus耗时: 4 ms
    insertSort耗时: 2 ms
    selectSort耗时: 3 ms
    //---1w---
    quickSort耗时: 2 ms
    mergeSort: 3 ms
    listSort耗时: 19 ms
    arraysSort耗时: 4 ms
    maoPaoSort耗时: 166 ms
    maoPaoSortPlus耗时: 122 ms
    insertSort耗时: 12 ms
    selectSort耗时: 52 ms
    
    //---10w---
    quickSort耗时: 14 ms
    mergeSort: 19 ms
    listSort耗时: 65 ms
    arraysSort耗时: 12 ms
    maoPaoSort耗时: 15242 ms
    maoPaoSortPlus耗时: 15044 ms
    insertSort耗时: 797 ms
    selectSort耗时: 4073 ms
    //---20w---
    quickSort耗时: 26 ms
    mergeSort: 34 ms
    listSort耗时: 102 ms
    arraysSort耗时: 60 ms
    maoPaoSort耗时: 60811 ms
    maoPaoSortPlus耗时: 60378 ms
    insertSort耗时: 3279 ms
    selectSort耗时: 15762 ms
    
    展开全文
  • 数据结构中常见几种排序算法

    千次阅读 多人点赞 2018-08-27 15:52:20
    数据结构中常见几种排序算法 快速排序 目录 数据结构中常见几种排序算法 快速排序 插入排序 希尔排序 归并排序 堆排序 选择排序 冒泡排序 基数排序 快速排序 基本思想: 基准分割法  a) 通过一趟...

     

     

    数据结构中常见的几种排序算法

    快速排序

    目录

    数据结构中常见的几种排序算法

    快速排序

    插入排序

    希尔排序

    归并排序

    堆排序

    选择排序

    冒泡排序

    基数排序


    快速排序

    基本思想: 基准分割法

     a) 通过一趟排序将要排序的数据分割成独立的两部分其中一部分所有的数据要比另外的一部分数据都要小

     b) 按照此方法对这两部分数据进行快速排序

     案例:3 6 5 8 4 2 1 9

       快排过程:3 6 5 8 4 2 1 9 => 2 1 |3| 6 5 8 4 9 => 1 |2| |3| 5 4 |6| 8 9 => 1 |2| |3| 4 |5| |6| |8| 9 => 1 2 3 4 5 6 8 9 

       改进的快排:随机快排

      思想:若对数组9 8 7 6 5 4 3 2 1进行快排,每次选取第一个元素作为基准元素,分组将很不均衡,这种极端情况将 导致时间复杂度和简单排序一样。为避免这样的极端情况,选取一个随机数作为基准元素

    步骤:

    a) 从数列中选一个元素 称“基准”

    b) 重新排列数列,所有元素比基准小的摆放在基准的前面,所有比基准大的元 `` 素摆放在基准后面,这个分区退出之后 基准就处于数列的中间位置,称为分区操作,

    c) 递归的把小于基准值元素的子数列和大于基准值元素的子数列排序

     

    //快速排序
    int QuickSort(int a[], int left,int right)
    {
    	int i = left, j = right, x = a[left];
    	while (i < j)
    	{
    		while (i<j && a[j]>x)
    			j--;
    		if (i < j)
    			a[i++] = a[j];
    
    
    	
    		while (i < j && a[i] < x)
    			i++;
    		if (i < j)
    			a[j--] = a[i];
    	a[i] = x;
    	QuickSort(a, left, right - 1);
    	QuickSort(a, left + 1, right);
    	}
    return 0;
    }

    插入排序

    基本原理 :

    构建有序序列,对于未排序数据 在已经排序序列中从后往前扫描,找到相应的位置进行插入,在从后向前的扫描过程中需要反复把已经排序的元素逐步向后挪位,为最新元素插入提供空间。

    步骤:

    a 从第一个元素开始,该元素可以认为已经被排序

    b 取出下一个元素 在已经排序的元素序列中从后向前扫描

    c 如果该元素(已排序)大于新元素,将该元素移到下一位置

    d 重复c步骤直到找到已排序的元素小于或者等于新元素的位置

    e 将新元素插入到该位置

    f 重复步骤b

    //插入排序
    void InsertSort(int a[], int size)
    {
    	for (int i = 0; i < size; i++)
    	{
    		int get = a[i];
    		int j = i - 1;
    		while (j>=0 && a[j]>get)
    		{
    			a[j + 1] = a[j];
    			j--;
    		}
    		a[j + 1] = get;
    	}
    }
    
    

    希尔排序

    增量排序,又叫递减增量排序,也是直接插入排序算法的一种高效的改进版本 是不稳定的

    基本思想 :

    将元素进行同余分组,比如元素个数有8个,若将其分为d1=4组,即每一个元素的下标进行模3运算,下标{0,4}模4余数都为0为一组,{1,5}余1 为一组,{2,6}余2为一组,{3,7}余3为一组,当然这只是一种逻辑上的划分,并不是物理上对其进行切分。然后在各组内进行直接插入排序,排序完再对其进行分组,一般取d(i+1) = ⌊d(i)/2⌋,此时的话d2=⌊d1/2⌋= 2组,就这样一直分组排序到di = 1并插入排序结束

     

     

    //希尔排序  高效的插入排序
    void ShellSort(int a[], int size)
    {
    	int h = 0;
    	while (h <= size)
    	{
    		h = h * 3 + 1;
    	}
    
    	while (h >= 1)
    	{	
    		for (int i = h; i < size; i++)
    		{
    			int j = i - h;
    			int get = a[i];
    			while (j >= 0 && a[j]>get)
    			{
    				a[j + h] = a[j];
    				j = j - h;
    			}
    			a[j + h] = get;
    		}
    		h = (h - 1) / 3;
    	}
    }

    归并排序

    采用分治法()

    基本思想:

    1)将已经有序的子序列合并,得到完全有序的序列,

    2)先使每个子序列有序,再使子序列段间有序

    3)若将两个有序表合并成一个有序表称为二路归并

     

    步骤:

    a 申请空间,让他大小为两个已经排序的序列之和,

    该空间用来存放合并后的序列

    b 设定两个指针,最初位置分别为两个已经排序序列起始位置

    c 比较两个指针所指向的元素,选择相对较小的放入合并空间,并移动

    指针到下一个位置

    d 重复步骤c 知道某个指针达到序列尾

    e 将另一个序列剩下的所有元素直接复制到合并序列尾。

    //归并排序
    void Merge(int a[], int left, int mid,int right)
    {
    	int size = right - left + 1;
    	int *temp = (int *)malloc(size*sizeof(int));
    	int i = left;
    	int j = mid + 1;
    	int index = 0;
    	while (i <= mid && j <= right)
    	{
    		temp[index++] = a[i] < a[j] ? a[i++] : a[j++];
    	}
    	while (i <= mid)
    	{
    		temp[index++] = a[i++];
    	}
    	while (j <= right)
    	{
    		temp[index++] = a[j++];
    	}
    	for (int k = 0; k < size; k++)
    	{
    		a[left++] = temp[k];
    	}
    }
    
    
    
    void MergeSort(int a[], int left, int right)
    {
    	if (left == right) return;
    	int mid = left + ((right - left) >> 1);
    	MergeSort(a, left, mid);
    	MergeSort(a, mid + 1, right);
    	Merge(a, left, mid, right);
    }

    堆排序

    利用堆 这种数据结构所设计的一种排序算法,也是选择排序的一种。

    a 可以利用数组的特点快速定位指定索引的元素

    b 堆分为大堆小堆 是完全二叉树

    大堆 要求每个节点的值都不大于其父节点的值即a[parent]>=a[i]

    在数组的非降序排序中,需要使用的就是大堆

    大堆中最大值肯定是在 堆顶的

    步骤:a 首先将序列构建称为大顶堆;

    (这样满足了大顶堆那条性质:位于根节点的元素一定是当前序列的最大值)

    b 取出当前大顶堆的根节点,将其与序列末尾元素进行交换;

    (此时:序列末尾的元素为已排序的最大值;由于交换了元素,当前位于根节点的堆并不一定满足大顶堆的性质)

    c 重复a.b步骤,直至堆中只有1个元素为止

     

    //堆排序
    void HeapModify(int a[], int i, int size)//向下调整
    {
    	int left_child = i * 2 + 1;//左孩子索引
    	int right_child = i * 2 + 2;//右孩子索引
    	int max = i;//选出当前节点与其左右孩子三者中最大值
    	if (left_child<size && a[left_child]>a[max])
    		max = left_child;
    	if (right_child<size && a[right_child]>a[max])
    		max = right_child;
    
    	if (max != i)
    	{
    		swap(a, i, max);//将当前节点与其最大子节点进行交换
    		HeapModify(a, max, size);// 递归调用 继续从当前节点向下进行堆调整
    	}
    }
    //建堆
    int BuildHeap(int a[], int size)
    {
    	int heap_size = size;
    	for (int i = (heap_size >> 1) - 1; i >= 0; --i)
    	{
    		HeapModify(a, i, heap_size);
    	}
    	return heap_size;
    }
    void HeapSort(int a[], int size)
    {
    	int heap_size = BuildHeap(a, size);//建大堆
    	while (heap_size > 1)
    	{
    		swap(a, 0, --heap_size);
    		HeapModify(a, 0, heap_size);//从新的堆顶元素开始向下调整,时间复杂度为O(lgn)
    	}
    }

    选择排序

    排序原理:

    a 首先在未排序序列中找到最小元素,存放到排序序列的起始位置,

    b 再从未排序元素中继续寻找最小元素,然后放到排序序列尾

    c 一次类推 直到所有元素都排序完毕

     

    //选择排序
    void SelectSort(int a[], int size)
    {
    	for (int i = 0; i < size-1; ++i)
    	{
    		int min = i;
    		for (int j = i + 1; j < size - 1; ++j)
    		{
    			if (a[j] < a[min])
    				min = j;
    		}
    		if (min != i)
    			swap(a, min, i);
    	}
    }

    冒泡排序

    排序原理:

    a)重复地走访过要排序的数列,一次比较两个元素,

    如果他们顺序错误就把他们交换过来

    b)走访数列的工作就是重复地进行 直到没有再需要交换,

    也就是说该数列已经排序完成

    c) 这个算法就是因为越小的元素会经由交换慢慢浮到数列的顶端

    步骤:

    1)将序列当中的左右元素,依次比较,保证右边的元素始终大于左边的元素;( 第一轮结束后,序列最后一个元素一定是当前序列的最大值;)

    2)对序列当中剩下的n-1个元素再次执行步骤1。

    3)持续每次对越来越少的元素进行重复上面的步骤直到没有任何一对数字需要比较

    void swap(int a[], int i, int j)
    {
    	int temp = a[i];
    	a[i] = a[j];
    	a[j] = temp;
    }
    //冒泡
    void BubbleSort(int a[], int size)
    {
    	for (int i = 0; i < size - 1; ++i)
    	{
    		for (int j = 0; j < size - 1 - i; ++j)
    		{
    			if (a[j] < a[j + 1]){
    				swap(a,j,j+1);
    			}
    		}
    	}
    }
    //鸡尾酒排序 分两部分1)将最大的元素放在后面 2)将最小的元素放在前面
    void Bubblesort(int a[], int size)
    {
    	int left = 0;
    	int right = size - 1;
    	while (left<right)
    	{
    		for (int i = 0; i < right; i++)
    		{
    			if (a[i]<a[i + 1])
    			{
    				swap(a, i, i + 1);
    			}
    		}
    		right--;
    		for (int j = right; j>left; j--)
    		{
    			if (a[j - 1] < a[j])
    			{
    				swap(a, j - 1, j);
    			}
    		}
    		left++;
    	}
    }

    基数排序

    基数排序:通过序列中各个元素的值,对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。

    分配:我们将L[i]中的元素取出,首先确定其个位上的数字,根据该数字分配到与之序号相同的桶中

    收集:当序列中所有的元素都分配到对应的桶中,再按照顺序依次将桶中的元素收集形成新的一个待排序列L[ ]

    对新形成的序列L[]重复执行分配和收集元素中的十位、百位...直到分配完该序列中的最高位,则排序结束

     

    附加上各种排序算法的稳定性以及空间/时间复杂度

     

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 常见几种排序算法

    2011-10-25 21:49:36
    常见几种排序算法源代码,很详细,很准确
  • 常见几种排序算法的实现:选择排序、插入排序、冒泡排序、希尔排序、快速排序、归并排序。包括实现与局测试。
  • 最近自己总结了js常见几种排序算法,并进行了简单的测试和对比。包括:冒泡排序,插入排序,选择排序,快速排序,归并排序等。 1.冒泡排序: 冒泡排序的原理如同其名,就是先对数组中的n个相邻元素进行两两比较,...
  • c++常见几种排序算法总结

    千次阅读 2016-08-14 13:11:03
    原文:c++常见几种排序算法总结 源代码下载地址:http://www.zuidaima.com/share/1829391352843264.htm 常见的几种排序:冒泡排序、鸡尾酒排序、直接插入排序、折半插入排序、快速排序、桶排序、鸽巢排序...
  • 常见几种排序算法的实现,希尔排序,冒泡排序、、、
  • 常见的7种排序算法

    万次阅读 多人点赞 2018-06-10 11:37:21
    最简单的一种排序算法。假设长度为n的数组arr,要按照从小到大排序。则冒泡排序的具体过程可以描述为:首先从数组的第一个元素开始到数组最后一个元素为止,对数组中相邻的两个元素进行比较,如果位于数组左端的元素...
  • java 几种常用排序算法 java 几种常用排序算法
  • 常见几种排序算法总结 上篇博客主要介绍了几种排序的算法思想及代码实现,本篇主要对上篇进行总结。 几种算法的时间复杂度及稳定性如下: (1)直接插入排序 适用场景:一般不用在数据大于1000的场合下...
  • Java几种排序算法

    2013-09-24 20:41:24
    java几种常见排序算法代码,包括冒泡,插入,快速等。
  • 几种常见排序算法

    千次阅读 2016-05-08 14:03:01
    本文介绍几种常见排序算法(选择排序,插入排序,希尔排序,归并排序,快速排序,堆排序),对算法的思路、性质、特点、具体步骤、java实现以及trace图解进行了全面的说明。最后对几种排序算法进行了比较和总结。
  • Java中常见几种排序算法

    千次阅读 2020-06-26 11:40:10
    本文主要记录了几种常见排序算法的Java实现,如冒泡排序、快速排序、直接插入排序、希尔排序、选择排序等等。 在学数据结构与算法时的部分记录,感觉好难啊╮(╯▽╰)╭,还需继续努力。 更多文章欢迎访问我的...
  • Java几种常见排序算法
  • 主要介绍了java几种排序算法的实现及简单分析,实例分析了插入排序、希尔排序、选择排序等常用排序算法,并分析了各个算法的优劣,需要的朋友可以参考下
  • 几种常见排序算法代码,附有其效率及分析
  • 常见几种排序算法 网页形式的,忘记什么时候找的了
  • 实现了直接插入排序、希尔排序、冒泡排序、快速排序、选择排序和堆排序等常见常用排序算法。方便你在完成其它项目时实现你想要的排序。希望能为你解决你遇到的问题。
  • 以下我们将介绍几种常见的排序,几种排序算法的时间复杂度及稳定性如下: 1、冒泡排序 冒泡排序的效率很低,但是算法实现起来很简单,因此很适合作为研究排序的入门算法。 基本思想 对当前还未排好序的...
  • 几种排序算法

    2015-01-25 17:15:00
    轻松学排序算法:眼睛直观感受几种常用排序算法 算法导论学习之快排+各种排序算法时间复杂度总结 快排时间复杂度分析 转载于:https://www.cnblogs.com/mountainfly/p/4248510.html...
  • 排序算法是一基本并且常用的算法。由于实际工作中处理的数量巨大,所以排序算法 对算法本身的速度要求很高。 而一般我们所谓的算法的性能主要是指算法的复杂度,一般用O方法来表示。在后面我将 给出详细的说明。
  • Java——常见几种排序算法

    万次阅读 2021-08-21 23:14:41
    一、冒泡排序 每次冒泡过程都是从数列的第一个元素开始,然后依次和剩余的元素进行比较, 跟列队一样, 从左到右两两相邻的元素比大小, 高的就和低的换一下位置. 最后最高(值最大)的肯定就排到后面了. 但是这只是把...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 175,196
精华内容 70,078
关键字:

常用的几种排序算法