插入排序

插入排序非常类似于整扑克牌。在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。
如果输入数组已经是排好序的话，插入排序出现最佳情况，其运行时间是输入规模的一个线性函数。如果输入数组是逆序排列的，将出现最坏情况。平均情况与最坏情况一样，其时间代价是Θ(n2)。也许你没有意识到，但其实你的思考过程是这样的：现在抓到一张7，把它和手里的牌从右到左依次比较，7比10小，应该再往左插，7比5大，好，就插这里。为什么比较了10和5就可以确定7的位置？为什么不用再比较左边的4和2呢？因为这里有一个重要的前提：手里的牌已经是排好序的。现在我插了7之后，手里的牌仍然是排好序的，下次再抓到的牌还可以用这个方法插入。编程对一个数组进行插入排序也是同样道理，但和插入扑克牌有一点不同，不可能在两个相邻的存储单元之间再插入一个单元，因此要将插入点之后的数据依次往后移动一个单元。
插入排序类似于整理扑克牌，从无序列中选择一个值插入到有序列中

冒泡排序

*** 冒泡排序法的基本思想：（以升序为例）含有n个元素的数组原则上要进行n-1次排序。对于每一躺的排序，从第一个数开始，依次比较前一个数与后一个数的大小。如果前一个数比后一个数大，则进行交换。这样一轮过后，最大的数将会出现称为最末位的数组元素。第二轮则去掉最后一个数，对前n-1个数再按照上面的步骤找出最大数，该数将称为倒数第二的数组元素......n-1轮过后，就完成了排序。***

快速排序

*** 快速排序是冒泡排序的一种改进，快速排序以一个基准值，将无序列分成两部分（左边小于基准值，右边大于基准值），然后递归。***
快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。

选择排序

选择排序：比如在一个长度为N的无序数组中，在第一趟遍历N个数据，找出其中最小的数值与第一个元素交换，第二趟遍历剩下的N-1个数据，找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，至此选择排序完成。
选择排序是根据找到无序数列中的最大或最小值插入到有序序列尾部来排序

地精排序

虽然没写过这个排序,但是个人感觉这个排序很有意思也很快速
号称最简单的排序算法,只有一层循环,默认情况下前进冒泡,一旦遇到冒泡的情况发生就往回冒,直到把这个数字放好为止

直接看它排序的过程,待排数组[6 2 4 1 5 9]

先设计一个标识i=0然后从头开始判断,什么时候(i < 6)不成立,什么时候排序结束,

所以,如何控制i的值是这个算法的关键

例如待排数组:

[6 2 4 1 5 9]

[0 1 2 3 4 5]

看一下具体的排序过程

[ i = 0 ]时啥也不干,先让i自增1,达到值为1才开始真正的比较

交换前[6 2 4 1 5 9][ i = 0]

交换后[6 2 4 1 5 9][ i = 1]



[ i = 1 ]比较6和2,发生交换,只要发生交换i就减1

  交换前[6 2 4 1 5 9][ i = 1]

交换后[2 6 4 1 5 9][ i = 0]



[ i = 0 ]又成0了,啥也不干,自增变成1再说

交换前[2 6 4 1 5 9][ i = 0]

交换后[2 6 4 1 5 9][ i = 1]



[ i = 1 ]再比较2和6,不交换,只要不要换就自增1

交换前[2 6 4 1 5 9][ i = 1]

交换后[2 6 4 1 5 9][ i = 2]



[ i = 2 ]比较6和4,发生交换,只要交换就减1

交换前[2 6 4 1 5 9][ i = 2]

交换后[2 4 6 1 5 9][ i = 1]



[ i = 1 ]比较2和4,不交换,只要不交换就自增1

交换前[2 4 6 1 5 9][ i = 1]

交换后[2 4 6 1 5 9][ i = 2]



[ i = 2 ]比较4和6,不交换,只要不交换就自增1

交换前[2 4 6 1 5 9][ i = 2]

交换后[2 4 6 1 5 9][ i = 3]



[ i = 3 ]比较6和1,交换,只要交换就减1

交换前[2 4 6 1 5 9][ i = 3]

交换后[2 4 1 6 5 9][ i = 2]



[ i = 2 ]比较4和1,交换,只要交换就减1

交换前[2 4 1 6 5 9][ i = 2]

交换后[2 1 4 6 5 9][ i = 1]



[ i = 1 ]比较2和1,交换,只要交换就减1

交换前[2 1 4 6 5 9][ i = 1]

交换后[1 2 4 6 5 9][ i = 0]



[ i = 0 ]时啥也不干,先让i自增1,达到值为1才开始真正的比较

交换前[1 2 4 6 5 9][ i = 0]

交换后[1 2 4 6 5 9][ i = 1]

[ i = 1]比较1和2,不交换,只要不交换就自增1

[ i = 2]比较2和4,不交换,只要不交换就自增1

[ i = 3]比较4和6,不交换,只要不交换就自增1

[ i = 4]比较6和5,交换,只要交换就减1

交换前[1 2 4 6 5 9][ i = 4]

交换后[1 2 4 5 6 9][ i = 3]

[ i = 3]比较4和5,不交换,只要不交换就自增1

[ i = 4]比较5和6,不交换,只要不交换就自增1

[ i = 5]比较6和9,不交换,只要不交换就自增1

[ i = 6]表达式(i < n)不成立,排序结束,

顺序输出结果即可:[ 1 2 4 5 6 9]
***************************************************************
    static void gnome_sort(int[] unsorted)
    {
        int i = 0;
        while (i < unsorted.Length)
        {
            if (i == 0 || unsorted[i - 1] <= unsorted[i])
            {
                i++;
            }
            else
            {
                int tmp = unsorted[i];
                unsorted[i] = unsorted[i - 1];
                unsorted[i - 1] = tmp;
                i--;
            }
        }
    }

两个经典文章

1 [排序算法]:http://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html
2[排序动画]:https://www.toptal.com/developers/sorting-algorithms/

经常使用的排序算法