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


		一、冒泡排序
1.1 概念
重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
1.2 运作
1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
平均时间复杂度    最差空间复杂度    最佳算法
О(n²)                    О(n²)                    NO
1.3 代码
[java]  
/** 
  * 冒泡排序 
  * 搜索整个值列，比较相邻元素，如果两者的相对次序不对，则交换它们 
  * @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 代码
 
[java]  
/** 
     * 选择排序: 
     * 搜索整个值列，以找到最小值。将该值与值列中第一个位置上的值进行交换。 
     * 搜索剩下的值列（第一个除外），以找到其中的最小值，然后将其与值列中第二个位置上的值进行交换。 
     * @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
[java]  
/** 
     * 插入排序: 
     * 前两个排序，然后降低三个与前两个排序；在将第四个与前三个排序，依次直至排序结束 
     * @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 概念
4.2 运作
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
1、插入排序在对几乎已经排好序的数据操作时，效率高， 即可以达到线性排序的效率
2、但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位<
平均时间复杂度                            最差空间复杂度       最佳算法
根据步长序列的不同而不同。       O(n)                       非最佳算法
 
 
五、快速排序
5.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）中，它至少会把一个元素摆到它最后的位置去。
 
5.2 运作
平均时间复杂度   &

补充：软件开发 , Java ,