排序算法

排序简单理解即为将一个数据元素的任意序列，重新排列成一个按关键字有序的序列

常用的排序算法有以下几类：插入排序（直接插入排序，希尔排序），选择排序（简单选择排序，堆排序），交换排序（冒泡排序，快速排序），归并排序，基数排序。排序方法选择得当与否直接影响程序执行的速度和辅助存储空间的占有量，进而影响整个软件的性能。下面对这些算法一一的介绍他们究竟是怎么排的。

1.直接插入排序
思路：逐个考察每个待排序元素，将每一个新元素插入到前面已经排好序的序列中适当的位置上，使得新序列仍然是一个有序序列

    class InsertSort {  
        public static void main(String[] args) {  
            int[] a = {1,5,3,8,4,3,8};  
            sort(a);  
            print(a);  
        }  
      
        private static void sort(int[] a) {  
            int temp;  
            for(int i=1; i<a.length; i++) {  
                int pos = i;        //确定位置，在此位置左边的数组是有序的。  
                temp = a[i];         //根据位置确定要插入的数值。  
                while(pos>0 && a[pos-1]>temp) {   //选择第一个不大于要插入数值的的位置  
                    a[pos] = a[pos - 1];   //将数据以此向后移动  
                    pos--;  
                }  
                a[pos] = temp;   //将指定数值插入恰当位置  
            }  
        }  
      
        private static void print(int[] a) {  
            for(int i: a) System.out.print(i + " ");  
            System.out.println();  
        }  
    }  

2.希尔排序
思路：首先将待排序的元素分为多个子序列，使得每个子序列的元素个数相对较少，对各个子序列分 别进行直接插入排序，待整个待排序序列“基本有序”后，再对所有元素进行一次直接插入排序

注意：希尔排序通过对数组 以一定间隔相隔的位置 进行插入排序，以达到让数据快速出现在它应该出现的位置的周围，使数组逐步接近基本有序。随着间隔的减少，数组越来越接近基本有序，最后间隔为1时，变成标准的插入排序。
数据的间隔有多种算法，一般要求间隔序列之间互质，此处使用Kunth序列：h = h * 3 + 1

    class ShellSort {  
        public static void main(String[] args) {  
            int[] a = {9,8,7,6,5,4,3,2,1};  
            sort(a);  
            println(a);  
        }  
      
        private static void println(int[] a) {  
            for(int i: a) System.out.print(i + " ");  
            System.out.println();  
        }  
      
        private static void sort(int[] a) {  
            int h = 1;  
            while(h <= a.length/3) h = h * 3 + 1;    //产成Kunth序列  
            while(h > 0) {  
                for(int i = h; i < a.length; i++) {  //对每个数据进行间隔为h的插入排序  
                        int pos = i;  
                        int temp = a[i];  
                        while(pos >= h && a[pos - h] > temp) {  
                            a[pos] = a[pos-h];  
                            pos -= h;  
                        }  
                        a[pos] = temp;  
                }  
                h = (h - 1) / 3;    //减小间隔值  
            }  
        }  
    }  

3.简单选择排序
思路：每一趟从 (i=1,2,…,n)个元素中选取一个关键字最小的元素作为有序序列中第 i 个元素

    class Select {  
        public static void main(String[] args) {  
            int[] a = {2,4,6,3,6,2,6,4,9};  
            sort(a);  
            print(a);  
        }  
      
        private static void sort(int[] a) {  
            int temp;  
            for(int i=0; i<a.length-1; i++) {  
                int min = i;  
                for(int j=i+1; j<a.length; j++) {  
                    if(a[j] < a[min]) min = j;  
                }  
                if(min != i) {  
                    temp = a[min];  
                    a[min] = a[i];  
                    a[i] = temp;  
                }  
            }  
        }  
      
        private static void print(int[] a) {  
            for(int i: a) System.out.print(i + " ");  
            System.out.println();  
        }  
    }  

4、堆排序
思路：堆排序，顾名思义，就是基于堆
堆分为最大堆和最小堆，其实就是完全二叉树。最大堆要求节点的元素都要大于其孩子，最小堆要求节点元素都小于其左右孩子，两者对左右孩子的大小关系不做任何要求，其实很好理解。有了上面的定义，我们可以得知，处于最大堆的根节点的元素一定是这个堆中的最大值。其实我们的堆排序算法就是抓住了堆的这一特点，每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆，依次类推，最终得到排序的序列。
或者说，堆排序将所有的待排序数据分为两部分，无序区和有序区。无序区也就是前面的最大堆数据，有序区是每次将堆顶元素放到最后排列而成的序列。每一次堆排序过程都是有序区元素个数增加，无序区元素个数减少的过程。当无序区元素个数为1时，堆排序就完成了。

堆分为大顶堆（父节点大于子节点）和小顶堆（父节点小于子节点），根节点是最大的节点（或者最小的节点），每次挑出根节点之后，将剩余的节点进行重新建堆。

    class Node {    //表示装数据的节点  
        private int key;    //排序的关键字  
        private Object value;   //数据  
          
        Node(int key, Object value) {  
            this.key =  key;  
            this.value = value;  
        }  
      
        int key() { return key; }  
        Object value() { return value; }  
    }  
      
    class Heap {  
        private Node[] array;   //序排序的数组  
        private int pos;    //当前有效数据的个数  
        Heap(Node[] array) {  
            this.array = array; //装入要排序的数组  
            pos = array.length;  
        }  
      
        private Node remove() { //删除堆的顶  
            Node result = array[0];  
            array[0] = array[--pos];    //将最后一个元素提至堆定  
            trickleDown(0);     //将堆顶下降为恰当位置  
            return result;  
        }  
      
        private void trickleDown(int index) {  
            Node top = array[index]; //存放要下降的数据  
            int left = getLeft(index);  //得到左子的位置  
            int right = getRight(index);    //得到右子的位置  
            int current;    //当前可能要下降的位置  
            if(left < pos && right < pos) //左右子节点有效，当前的位置设置为左右子节点中小的那个  
                current = array[left].key() > array[right].key() ? left : right;  
            else if (left < pos) current = left; //如果左子节点有效，则当前位置设置为左子节点  
            else current = -1;  //没有可以下降的位置  
            while(current != -1 && array[current].key() > top.key()) {//当前节点有效且大于要下降的数据  
                array[index] = array[current];  //将当前节点向上提升。  
                index = current;    //重复以上过程  
                left = getLeft(index);  
                right = getRight(index);  
                if(left < pos && right < pos)   
                    current = array[left].key() > array[right].key() ? left : right;  
                else if (left < pos) current = left;   
                else current = -1;  
            }  
            array[index] = top; //将暂存的数据放入恰当的位置  
        }  
      
        private int getParent(int index) {  
            return (index-1)/2;  
        }  
      
        private int getLeft(int index) {  
            return 2 * index + 1;  
        }  
      
        private int getRight(int index) {  
            return 2 * index + 2;  
        }  
      
        public void sort() {  
            for(int i=array.length/2 -1; i>=0; i--) {  
                trickleDown(i);  
            }  
            for(int i=array.length-1; i>=0;i--) array[i] = remove();  
        }  
      
        public static void main(String[] args) {  
            Node[] nodes = {new Node(50,"hello"),   
                new Node(20,"jason"),  
                new Node(60,"peter"),   
                new Node(50,"orange"),  
                new Node(30,"temp"),   
                new Node(40,"hello"),  
                new Node(90,"nasen"),  
                new Node(25,"kaka")};  
            Heap heap = new Heap(nodes);  
            heap.sort();  
            print(nodes);  
        }  
      
        private static void print(Node[] nodes) {  
            for(Node node: nodes)   
                System.out.println(node.key() + "-----" + node.value());  
        }  
    }  

5、冒泡排序
思想：交换类排序主要是通过两两比较待排元素的关键字，若发现与排序要求相逆，则“交换”之

    class Bubble {  
        public static void main(String[] args) {  
            int[] a = {6,3,2,6,3,2,9,7};  
            sort(a);  
            print(a);  
        }  
      
        private static void print(int [] a) {  
            for(int i: a) System.out.print(i + " ");  
            System.out.println();  
        }  
      
        private static void sort(int[] a) {  
            int temp;  
            for(int i=a.length-1; i>0; i--) {  
                for(int j=0; j<i; j++) {  
                    if(a[j] > a[j+1]) {  
                        temp = a[j];  
                        a[j] = a[j+1];  
                        a[j+1] = temp;  
                    }  
                }  
            }  
        }  
    }  

6、快速排序
思想：选 出一个关键字，比他小的放到他的左边，大的放到右边，设置两个指针，同时与关键字进行比较。举个例子：期末考试到了，考试完了我们要把成绩排序，我们先选 60为几个分数，大于等于60分的排到一边，小于60分的排到另一边，之后对小于60分的同学和大于60分的同学进行同样的排序。

    class Quick {  
        public static void main(String[] args) {  
            int[] a = {6,9,5,4,2,45,23,45,53,3,7};  
            int pos = getPartitionPos(a,0,a.length);  
            sort(a,0,a.length);  
            println(a);  
        }  
      
        public static void println(int[] a) {  
            for(int i: a) System.out.print(i + " ");  
            System.out.println();  
        }  
      
        public static void sort(int[] a,int begin, int end) {  
            if(begin >= end) return;  
            int pos = getPartitionPos(a,begin,end);  
            sort(a,begin,pos);  
            sort(a,pos + 1, end);  
        }  
      
        private static int getPartitionPos(int[] a, int begin, int end) {  
            int pos = begin;  
            int value = a[begin];  
            while(true) {  
                while(begin < end && a[--end] > value);   //从结尾向左找到第一个比枢纽小的数值  
                while(begin < end && a[++begin] < value); //从结尾向右找到第一个比枢纽大的数值  
                if(begin < end) { //如果需交互  
                    a[pos] = a[end];    //将比枢纽小的值放在空位  
                    a[end] = a[begin];  //将比枢纽大的值放在原来从右向左第一个比枢纽小的值的位置上  
                    pos = begin;    //将从左向右第一个比枢纽大的值的位置标志为空位  
                } else break;   
            }  
            if(pos != begin) { //如果空位与结束位置不等  
                a[pos] = a[begin];  //将空位置为结束时位置的值  
                a[begin] = value;   //将结束位置放置枢纽  
            } else a[pos] = value;    
            return begin;  
        }  
    }  

7、归并排序
思路：就是相邻两个元素组成一个组，组内进行排序，之后再将组内元素增加，循环比较
1.划分：将待排序的序列划分为大小相等（或大致相等）的两个子序列；
2.治理：当子序列的规模大于 1 时，递归排序子序列，如果子序列规模为 1 则成为有序序列；
3.组合：将两个有序的子序列合并为一个有序序列。

    class Merge {  
        public static void main(String[] args) {  
            int[] a = {3,2,5,2,0,6,3,7};  
            sort(a,0,a.length);  
            print(a);  
        }  
      
        public static void sort(int[] a, int p1, int p3) {  
            if((p3-p1) <= 1) return; //判断是否不需要继续递归  
      
            int p2 = (p3 + p1)/2; //计算中间位置p2  
      
            sort(a,p1,p2); //将p1 ~ p2之间递归排序  
            sort(a,p2,p3); //将p2 ~ p3之间递归排序   
              
            merge(a,p1,p2,p3); //合并p1~p2,p2~p3  
        }  
      
        public static void merge(int[] a, int p1, int p2 ,int p3) {  
            int[] c = new int[p3 - p1];  
            int n = p1, m = p2, i = 0;  
            while(n< p2 && m<p3) {  
                if(a[n] < a[m]) c[i++] = a[n++];  
                else c[i++] = a[m++];  
            }  
            while(n < p2) c[i++] = a[n++];  
            while(m < p3) c[i++] = a[m++];  
      
            for(int j=0; j<c.length; j++) a[p1 + j] = c[j];   
        }  
      
        public static void print(int[] c) {  
            for(int i: c) System.out.print(i + " " );  
            System.out.println();  
        }  
      
    }  

8、基数排序
思路：就是先对个位进行比较，进行排序，再对十位进行比较，进行排序……最后对最高位进行比较，进行排序。举个例子：每年在大学里我们都要进行评优，什么样的学生是最优的学生？各方面都要进行比较——成绩、人品、道德等

    class Queue {     
        int[] values;     
        int head = -1;     
        int tail = -1;     
        Queue(int size) {   values  = new int[size]; }     
        boolean isEmpty() { return head == tail; }     
        void put(int value) {   values[++head] = value; };     
        int get() { return values[++tail]; };     
        void clean() { head = -1; tail = -1; }     
    }     
        
    class Radix {     
        public static void main(String[] args) {     
            int[] a = {6,4,3,2,4,1,2};     
            sort(a,4);     
            println(a);     
        }     
        
        /**   
         * @param radix 2的幂   
         * @param a 源数据数组   
         */    
        public static void sort(int[] a,int radix) {     
            int base = 1<<radix;     
            Queue[] q = new Queue[base];     
            for(int i=0; i<base; i++) {           
                q[i] = new Queue(a.length);     
            }     
        
            int bit = 0;     
            int sum;     
            do {     
                sum = 0; //判断是否要再继续     
                for(int i: a) {     
                    int remain = i >> bit;     
                    q[remain&(base - 1)].put(i);     
                    sum |= remain;     
                }     
                bit += radix;     
                //从队列中取出数据，放入原数组中     
                int i = 0;     
                for(int j=0; j<q.length; j++) {     
                    while(!q[j].isEmpty()) a[i++] = q[j].get();     
                    q[j].clean();     
                }     
            } while(sum > 0);     
        }     
        
        public static void println(int[] a) {     
            for(int i: a) System.out.print(i + " ");     
            System.out.println();     
        }     
    }