排序算法有很多种，接来下数理一下各种排序算法。
算法是否稳定是否为原地排序时间复杂度空间复杂度备注选择排序否是N21插入排序是是介于N和N2之间1取决于输入元素的排序情况希尔排序否是NlogN1快速排序否是N6/5lgN运行效率由概率提供保证三向快速排序否是介于N和NlogN之间lgN运行效率由概率保证，同时也取决于输入元素的分布情况归并排序是否NlogNN堆排序否是NlogN1根据上表可以看出： 1. 只有插入排序和归并排序具有稳定的特点。 2. 只有归并排序不具有原地排序的特点。
原地排序就是指不申请多余的空间来进行的排序，就是在原来的排序数据中比较和交换的排序。
下面介绍一下各种排序方法。
选择排序是最简单的排序算法。首先找到数组中最小的那个元素，然后将最小的元素与第一个元素的位置进行交换。在剩余的数组中找到最小的元素，再与第二个元素位置进行交换。选择排序总是在不断地选择剩余元素的最小者。
public class Selection { public static void sort(Integer[] a){ int N = a.length; for(int i=0; i<N; i++){ int min = i; for(int j=i+1; j<N; j++){ if(less(a[i], a[j])) min = j; } exch(a, i, min); } } private static void exch(Integer[] a, int i, int min) { // TODO Auto-generated method stub Integer tem = a[i]; a[i] = a[min]; a[min] = tem; } private static boolean less(Integer Integer, Integer Integer2) { // TODO Auto-generated method stub if (Integer > Integer2) return true; else return false; } private static void show(Integer[] a) { // TODO Auto-generated method stub Integer N = a.length; for(int i=0; i<N; i++){ System.out.print(a[i]+" "); } System.out.println(" "); } public static void main(String[] args){ Integer[] a = {1, 4, 2, 5, 3, 0, 9, 7, 6, 8}; System.out.println("befor sotred:"); show(a); sort(a); System.out.println("after sotred:"); show(a); } }输出结果
befor sotred: 1 4 2 5 3 0 9 7 6 8 after sotred: 0 1 2 4 3 5 8 6 7 9总的来说，选择排序是一种很容易实现和理解的算法。它有两个特点： 1. 运行时间和输入无关。 2. 数据移动最少。
插入排序类似于整理桥牌的过程，将每一张牌依次一张一张插入其他有序的牌序中。 插入排序的时间与输入数组中的元素初始顺序有关。
package com.alorithms.sorting; public class Insertion { public static void sort(Integer[] a){ int N = a.length; for(int i=1; i<N; i++){ for(int j=i ; j>0 && less(a[j], a[j-1]); j--){ exch(a, j, j-1); } } } private static void exch(Integer[] a, int j, int i) { // TODO Auto-generated method stub Integer tem = a[j]; a[j] = a[j-1]; a[j-1] = tem; } private static boolean less(Integer integer, Integer integer2) { // TODO Auto-generated method stub if (integer<integer2) return true; else return false; } public static void main(String[] args){ Integer[] a = {1, 4, 2, 5, 3, 0, 9, 7, 6, 8}; System.out.println("befor sotred:"); show(a); sort(a); System.out.println("after sotred:"); show(a); } private static void show(Integer[] a) { // TODO Auto-generated method stub Integer N = a.length; for(int i=0; i<N; i++){ System.out.print(a[i]+" "); } System.out.println(" "); } }当倒置的数量很少时，插入排序可能比其他任何算法都要快。
希尔排序是基于插入排序的一种快速排序方法。希尔排序的思想是尽量的把输入初始数组变得有序，这样在插入排序的过程中速度就会提高很多。
希尔排序按照步长把输入数组分为几组，每组内部进行排序，然后缩短步长，每组内部继续进行排序，最终步长为1再排序，得到最后的结果。
import java.util.Scanner; public class Shell { public static void sort(Integer[] a){ int N = a.length; int h = 1; while(h<N/3){ h = 3*h +1; } while(h>=1){ for(int i=h; i<N; i++){ for(int j=i; j>=h&&less(a[j], a[j-h]); j-=h){ exch(a, j, j-h); } } h =h/3; } } private static void exch(Integer[] a, int j, int i) { // TODO Auto-generated method stub Integer tem = a[i]; a[i] = a[j]; a[j] = tem; } private static boolean less(Integer integer, Integer integer2) { // TODO Auto-generated method stub if (integer<integer2) return true; else return false; } public static void main(String[] agrs){ int n = 10; Scanner sc = new Scanner(System.in); Integer[] a = new Integer[n]; for(int i=0; i<n; i++){ int b = sc.nextInt(); a[i] = b; } System.out.println("befor sotred:"); show(a); sort(a); System.out.println("after sotred:"); show(a); } private static void show(Integer[] a) { // TODO Auto-generated method stub Integer N = a.length; for(int i=0; i<N; i++){ System.out.print(a[i]+" "); } System.out.println(" "); } }希尔排序比插入排序和选择排序都要快得多，并且数组越大，优势越明显。
