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

一、冒泡排序

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

 

未完待续

评论

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; 
                } 
                 
            } 
        }