各种排序，一网打尽！

说到排序，大家都不陌生
有点编程基础的人都懂哈哈
各种各样的排序，你懂的程度有多少呢
排序之间又有什么关联了
这篇文章我谈谈我的理解

简单排序！

Comparable接口

比如学生的排序，按照年龄或者身高
实现Comparable接口的类进行的排序
这里我图省事，写的很简单，说明问题就行，一看便懂！

public class Student implements Comparable<Student>{
	public int age;
	@Override
	public int compareTo(Student s){
		return this.age-s.age;
	}
}

@Test
public Comparale getMax(Compareble c1,Comparable c2){
	int cmp=c1.compareTo(c2);
	if(cmp>0){return c1;}
	else{return c2;}
}

冒泡排序

1.比较相邻元素，要是后面比前面小，则交换位置
2.从开始到末尾，每一组都这样比对
熟悉的配方！

def bubble(l):
    for i in range(len(l)):
        for j in range(len(l)-i-1):
            if l[j] > l[j+1]:
                l[j], l[j+1] = l[j+1], l[j]
l = [9, 8, 7, 2, 3]
bubble(l)
print(l)

想象一下这个过程，冒泡，每一次循环，最大的数就冒到最后了
j 的范围为什么是len（l）-1-i？
因为每一次循环之后，最后那个数已经最大了，不需要再比对他和她前面的数 的大小了！
比较的次数为：
(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2;
交换的次数为：
(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2;
时间复杂度为O(N^2).

选择排序

每次排序，假定第一个是最小，然后遍历，如果有比当前小的，就记下他的位置，遍历完后交换
交换完后再遍历，上一层第一个已经不用处理了，所以第一个其实时这一层的第二个。。。

def selectSort(l):
    for i in range(len(l)):
        minindex=i
        for j in range(i+1,len(l)):
            if l[j]<l[minindex]:
                minindex=j
        if i!=minindex:
            l[i],l[minindex]=l[minindex],l[i]
    
    return l

比较的次数为：
(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;
交换的次数为：
N-1;
时间复杂度为O(N^2).
其实这里有一个优化，就是 i 的循环次数，考虑一下

插入排序

所有元素分为排好序的和未排序的，每次从未排序的元素中找第一个元素，插入到排序组中

def insertsort(arr):
    for i in range(len(arr)):
        for j in range(i,0,-1):
            if arr[j-1]>arr[j]:
                arr[j-1],arr[j]=arr[j],arr[j-1]
    return arr

l=insertsort([9,8,7,2,1])
print(l)

比较的次数为：
(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2;
交换的次数为：
(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2;
时间复杂度为O(N^2).

高级排序

希尔排序

是插入排序的进阶版本，在插入排序中，我们对比未排序的元素在排序元素组中的位置的时候，每次从最后往前一个一个比较，
所以新的改进是，每次跳跃着比较，把步进从1可以变大一点，这样会提高效率

def shellsort(l):
    h=1
    while(h<len(l)/2):
        h=2*h+1
    while(h>=1):
        for i in range(h,len(l)):
            for j in range(i,h-1,-1):
                if l[j-h]>l[j]:
                    l[j-h],l[j]=l[j],l[j-h]

        h=int(h/2)
    return l

l=shellsort([9,8,7,4,6])
print(l)

选定一个gap，然后以这个gap划分组，每组两个成员，进行插入排序
每一轮使得gap减小为一半，直到为1.

归并排序

利用递归的思想
1.尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止。
2.将相邻的两个子组进行合并成一个有序的大组；
3.不断的重复步骤2，直到最终只有一个组为止。

class mergesort(object):

    def merge(self, l, lo, hi):

        mid = int((lo+hi)/2)
        left = []
        right = []
        for i in range(lo, mid+1):
            left.append(l[i])
        for i in range(mid+1, hi+1):
            right.append(l[i])

        p1 = 0
        p2 = 0
        i = lo
        while p1 < len(left) and p2 < len(right):
            if left[p1] < right[p2]:
                l[i] = left[p1]
                i += 1
                p1 += 1
            else:
                l[i] = right[p2]
                i += 1
                p2 += 1
        while p1 < len(left):
            l[i] = left[p1]
            i += 1
            p1 += 1
        while p2 < len(right):
            l[i] = right[p2]
            i += 1
            p2 += 1

    def sort(self, l, lo, hi):
        if lo == hi:
            return
        mid = int((lo+hi)/2)
        self.sort(l, lo, mid)
        self.sort(l, mid+1, hi)
        self.merge(l, lo, hi)

快速排序

1.首先设定一个分界值，通过该分界值将数组分成左右两部分；
2.将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于
或等于分界值，而右边部分中各元素都大于或等于分界值；
3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两
部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当
左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

def sort(arr, lo, hi):
    if hi <= lo:
        return
    part = partition(arr, lo, hi)
    #print(part)
    sort(arr, lo, part-1)
    sort(arr, part+1, hi)


def partition(arr, lo, hi):
    left = lo+1
    right = hi
    key = arr[lo]
    while True:
        while key < arr[right]:
            right -= 1
            if right == lo:
                break
        while key > arr[left]:
            left += 1
            if left == hi:
                break
        if left >= right:
            break
        else:
            arr[left], arr[right] = arr[right], arr[left]
    arr[lo], arr[right] = arr[right], arr[lo]
    #print(arr)
    return right

堆排序

对构造好的堆，我们只需要做类似于堆的删除操作，就可以完成排序。
1.将堆顶元素和堆中最后一个元素交换位置；
2.通过对堆顶元素下沉调整堆，把最大的元素放到堆顶(此时最后一个元素不参与堆的调整，因为最大的数据已经到了数组的最右边)
3.重复1~2步骤，直到堆中剩最后一个元素。

public class HeapSort {
    private static boolean less(Comparable[] heap, int i, int j) {
        return heap[i].compareTo(heap[j]) < 0;
    }

    private static void exch(Comparable[] heap, int i, int j) {
        Comparable tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }

    private static void createHeap(Comparable[] source, Comparable[] heap) {
        System.arraycopy(source, 0, heap, 1, source.length);
        for (int i = (heap.length) / 2; i > 0; i--) {
            sink(heap,i,heap.length-1);
        }
    }

    private static void sort(Comparable[] source){
        Comparable[] heap = new Comparable[source.length + 1];
        createHeap(source,heap);
        int N=heap.length-1;
        while (N!=1){
            exch(heap,1,N);
            N--;
            sink(heap,1,N);
        }
        System.arraycopy(heap,1,source,0, source.length);
    }

    private static void sink(Comparable[] heap, int target, int range) {
        while (2*target<=range){
            int max;
            if(2*target+1<=range){
                if(less(heap,2*target,2*target+1)){
                    max=2*target+1;
                }else {
                    max=2*target;
                }
            }else {
                max=2*target;
            }

            if(!less(heap,target,max)){
                break;
            }
            exch(heap,target,max);
            target=max;
        }
    }

    public static void main(String[] args) {
        String[] arr={"s","o","d","r","b"};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}