排序算法

十大经典排序算法最强总结（含JAVA代码实现）

动画10大算法

https://github.com/hustcc/JS-Sorting-Algorithm

坐在马桶上看算法系列

1. 冒泡排序

冒泡排序

2. 选择排序

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕

选择排序

3. 插入排序（Insertion Sort）

特点：不需要占用额外的空间

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

插入排序

4. 希尔排序（TODO）

5. 归并排序（重要）

演示

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

对链表的归并排序

leetcode

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        //归并排序
        if(head==null || head.next==null){
            return head;
        }

        //找到中间节点，然后递归对两边排序
        //使用快慢指针找中间节点
        ListNode slow=head, fast=head, pre=head;
        while(fast != null && fast.next !=null){
            pre=slow;
            slow=slow.next; //一次移动一步
            fast=fast.next.next; //一次移动两步
        }
        pre.next=null; //必须要置null，将链表分为两段

        return merge(sortList(head), sortList(slow));
    }

    //归并排序
    public ListNode merge(ListNode l1, ListNode l2){
        if(l1==null || l2==null){
            return l1==null?l2:l1;
        }

        ListNode dummy=new ListNode(0);
        ListNode cur=dummy;
        while(l1!=null && l2!=null){
            if(l1.val >= l2.val){
                cur.next=l2;
                l2=l2.next;
            }else{
                cur.next=l1;
                l1=l1.next;
            }
            cur=cur.next;
        }

        if(l1 !=null){
            cur.next=l1;
        }

        if(l2 !=null){
            cur.next=l2;
        }

        return dummy.next;
    }
}

对数组的归并排序

/**
 * 归并排序
 * 
 * @param array
 * @return
 */
public static int[] MergeSort(int[] array) {
    if (array.length < 2) return array;
    int mid = array.length / 2;
    int[] left = Arrays.copyOfRange(array, 0, mid);
    int[] right = Arrays.copyOfRange(array, mid, array.length);
    return merge(MergeSort(left), MergeSort(right));
}
/**
 * 归并排序——将两段排序好的数组结合成一个排序数组
 *
 * @param left
 * @param right
 * @return
 */
public static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];

    //i和j分别代表 left和Right的索引
    for (int index = 0, i = 0, j = 0; index < result.length; index++) {
        if (i >= left.length) {             //left没数据了
            result[index] = right[j++];
        } else if (j >= right.length){      //right没数据了
            result[index] = left[i++];
        } else if (left[i] > right[j]){     
            result[index] = right[j++];    
        }else{
            result[index] = left[i++];
        }
    }
    return result;
}

6. 快速排序（Quick Sort：重要）

坐在马桶上看算法：快速排序

要点：

找基准点：pivot (默认找第一个就可以)；

从两头找数值(分别是大于基准值和小于基准值)，然后交换；

直到哨兵碰头，然后和pivot交换

递归

先从右往左找一个小于6的数，再从左往右找一个大于6的数

找到之后，交换

哨兵碰头，然后和pivot交换

递归

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

示例