`
雪馨25
  • 浏览: 129583 次
  • 性别: Icon_minigender_2
  • 来自: 北京
社区版块
存档分类
最新评论

算法--排序(冒泡,选择,插入,快速)

阅读更多

一、冒泡排序

1.1 概念
重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
1.2 运作
1、比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤,除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
平均时间复杂度    最差空间复杂度    最佳算法

О(n²)                    О(n²)                    NO
1.3 代码

    /** 
      * 冒泡排序 
      * 搜索整个值列,比较相邻元素,如果两者的相对次序不对,则交换它们 
      * @param numbers 待排序数据 
      * @return 
      */  
     private void maoPao(int[] numbers) {  
         for(int i = numbers.length-1;i>=0;i--){//循环所有未排序数据  
             for(int j=0;j<i;j++){//两两比较  
                 if(numbers[j]>numbers[j+1]){  
                     int temp = numbers[j];  
                     numbers[j]=numbers[j+1];  
                     numbers[j+1]=temp;  
                 }  
             }  
         }  
     }  
 

二、选择排序
2.1 概念

首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾(目前已被排序的序列)。以此类推,直到所有元素均排序完毕。
2.2 运作
1、所有序列中找到最大的放第一位
2、除去第一位,剩余所有序列中找到最大的放第二位
3、以此类推直至排序完成

平均时间复杂度    最差空间复杂度                  最佳算法

О(n²)                      О(n) total, O(1)auxiliary         偶尔出现

2.3 代码

    /** 
         * 选择排序: 
         * 搜索整个值列,以找到最小值。将该值与值列中第一个位置上的值进行交换。 
         * 搜索剩下的值列(第一个除外),以找到其中的最小值,然后将其与值列中第二个位置上的值进行交换。 
         * @param numbers 待排序数据 
         * @return 
         */  
        private void xuanZe(int[] numbers) {  
            for(int i = 0 ; i <numbers.length ;i++){  
                int max = i;  
                for(int j = i+1 ; j <numbers.length-1 ;j++){  
                    if(numbers[j]<numbers[max]){  
                        max = j;  
                    }  
                }  
                if(max != i){  
                    int temp = numbers[i];  
                    numbers[i]=numbers[max];  
                    numbers[max]=temp;  
                }  
                  
            }  
        }  
 

三、插入排序
3.1 概念
工作原理是通过构建有序序列, 对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排 序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
3.2 运作
1、从第一个元素开始,该元素 可以认为已经被排序2、取出下一个元素,在已经排序的元素序列中从后向前扫描3、如果该元素(已排序)大于新元素,将该元素移到下一位置4、重复步骤3, 直到找到已排序的元素小于或者等于新元素的位置5、将新元素插入到该位置后6、重复步骤2~5
平均时间复杂度    最差空间复杂度                            最佳算法

О(n²)                        总共O(n) ,需要辅助空间O(1)     No

3.3 代码

    /** 
         * 插入排序: 
         * 前两个排序,然后降低三个与前两个排序;在将第四个与前三个排序,依次直至排序结束 
         * @param numbers 待排序数据 
         * @return 
         */  
        private void chaRu(int[] numbers) {  
            for(int i = 1 ; i <numbers.length ;i++){  
                int one = numbers[i];  
                for(int j = i-1;j>=0;j--){  
                    if(numbers[j]>one){  
                        numbers[j+1]=numbers[j];  
                        numbers[j]=one;  
                    }  
                }  
            }  
        }  

 

四、快速排序

4.1 概念 快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。
步骤为:
      1)设置两个变量I、J,排序开始的时候:I=1,J=N;
  2)以第一个数组元素作为关键数据,赋值给X,即 X=A[1];
  3)从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于X的值,让该值与X交换;
  4)从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于X的值,让该值与X交换;
  5)重复第3、4步,直到 I=J;

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

4.2 运作

平均时间复杂度    最差空间复杂度                         最佳算法

Ο(n log n)                根据实现的方式不同而不同      有时是

4.3 代码
    public void kuaiSu(int[] pData,int left,int right){      
          int temp;     
          int i = left;     
          int j = right;     
          int middle = pData[left];     
          while(true){     
              while((++i)<right-1 && pData[i]<middle);     
              while((--j)>left && pData[j]>middle);     
              if(i>=j)     
                  break;     
              temp = pData[i];     
              pData[i] = pData[j];     
              pData[j] = temp;     
          }       
          pData[left] = pData[j];     
          pData[j] = middle;          
          if(left<j)      
              kuaiSu(pData,left,j);     
          if(right>i)      
              kuaiSu(pData,i,right);     
        }    

学习参考:

http://tscjsj.blog.51cto.com/412451/84587

http://tscjsj.blog.51cto.com/412451/84590

 

未完待续

2
1
分享到:
评论
1 楼 308202251 2013-01-09  
    /**
         * 选择排序:
         * 搜索整个值列,以找到最小值。将该值与值列中第一个位置上的值进行交换。
         * 搜索剩下的值列(第一个除外),以找到其中的最小值,然后将其与值列中第二个位置上的值进行交换。
         * @param numbers 待排序数据
         * @return
         */ 
        private void xuanZe(int[] numbers) { 
            for(int i = 0 ; i <numbers.length ;i++){ 
                int max = i; 
                for(int j = i+1 ; j <numbers.length;j++){ 
                    if(numbers[j]<numbers[max]){ 
                        max = j; 
                    } 
                } 
                if(max != i){ 
                    int temp = numbers[i]; 
                    numbers[i]=numbers[max]; 
                    numbers[max]=temp; 
                } 
                 
            } 
        }

相关推荐

Global site tag (gtag.js) - Google Analytics