1.3.2 快速排序

1.3.2.1 定义

快速排序一听这个名字可能感觉很快，但是算法时间复杂度最坏情况却跟插入排序是一 样的。之所以成为快速排序是因为他的平均效率比堆排序还要快，快速排序也是基于分治思想与归并排序差不多，但是快速排序是原址的，直接在原数组操作不需要再开辟新的存储空间。快速排序的思想很简单，就是选定一个关键字k将原数组分成两份g1与g2，g1中所有的元素都比k小或者相等，而g2中所有的数据都比k大或者等于，这样对g1与g2分别进行快速排序，最终我们得到的就是一个有序的数组。

基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分
如图所示：

方法其实很简单：分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即=10），指向数字

1.3.2.2 java实现

public class quickSort {  
  public static void main(String[] args) {
        int a[] = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51};
        if (a.length > 0) {    //查看数组是否为空
            _quickSort(a, 0, a.length - 1);
        }
        System.out.println(Arrays.toString(a));
    }
    public static void _quickSort(int[] list, int low, int high) {
        if (low < high) {
            int middle = getMiddle(list, low, high);  //将list数组进行一分为二
            _quickSort(list, low, middle - 1);        //对低字表进行递归排序
            _quickSort(list, middle + 1, high);       //对高字表进行递归排序
        }
    }

    public static int getMiddle(int[] list, int low, int high) {
        int tmp = list[low];    //数组的第一个作为中轴
        while (low < high) {
            while (low < high && list[high] >= tmp) {
                high--;
            }
            list[low] = list[high];   //比中轴小的记录移到低端
            while (low < high && list[low] <= tmp) {
                low++;
            }
            list[high] = list[low];   //比中轴大的记录移到高端
        }
        list[low] = tmp;              //中轴记录到尾
        return low;                   //返回中轴的位置
    }
}

或者如下：

	@Test
    public void testQuickDemo(){
        int a[] = {49, 38, 65, 97, 76, 13, 27, 1};
        sort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    public void sort(int[] map, int start, int end) {
        if (start < end) {
            System.out.println("开始"+Arrays.toString(map));
            int p = getPlocation(map, start, end);
            System.out.println("p====="+p);
            sort(map, start, p - 1);
            sort(map, p + 1, end);
            System.out.println("结束"+Arrays.toString(map));
        }
    }
    public int getPlocation(int[] map, int start, int end) {
        int core = map[end];
        int i = start - 1;
        for (int j = start; j <= end - 1; j++) {
            if (map[j] <= core) {
                i++;
                int cache = map[j];
                map[j] = map[i];
                map[i] = cache;
            }
        }
        i++;
        map[end] = map[i];
        map[i] = core;
        return i;
    }

1.4 归并排序

1.4.1 定义

基本排序：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列
如图所示：

1.4.2 java实现

import java.util.Arrays;  
  
public class MergeSortDemo{  
int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};  
public  mergingSort(){  
    sort(a,0,a.length-1);  
    for(int i=0;i

import java.util.ArrayList;  
  
import java.util.List;         
public class radixSort {    
         int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,25,53,51};  
  
public radixSort(){    
         sort(a);    
         for(int i=0;imax){      
               max=array[i];       
                    }       
                 }                               
        int time=0;       
         //判断位数;       
                 while(max>0){       
                    max/=10;       
                     time++;       
                 }                               
        //建立10个队列;       
                 List queue=new ArrayList();       
                 for(int i=0;i<10;i++){       
                          ArrayList queue1=new ArrayList();     
                     queue.add(queue1);       
        }                              
                         //进行time次分配和收集;     
                 for(int i=0;i queue2=queue.get(x);   
                             queue2.add(array[j]);   
                             queue.set(x, queue2);    
            }     
                      int count=0;//元素计数器;       
            //收集队列元素;       
                     for(int k=0;k<10;k++){     
                while(queue.get(k).size()>0){    
                         ArrayList queue3=queue.get(k);    
                             array[count]=queue3.get(0);       
                             queue3.remove(0);    
                    count++;    
              }       
            }       
         }     
    }      
}