八大排序（尚未完善）

基本的流程就不写了，不会就自己看代码，按照代码跑6、7遍就懂了

java的数组值交换

异或交换运算（需要保证位置不同）：

public static void swap(int[] arr, int i, int j){
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];      
}

1. 冒泡排序

时间复杂度O(N^2)，额外空间复杂度O(1)

public static void bubbleSort(int[] arr){
        if(arr == null || arr.length < 2)
            return;
        for(int e = arr.length - 1; e > 0; e--)
           for(int i = 0; i < e; i++){
                if(arr[i] > arr[i + 1])
                   swap(arr, i, i + 1);
            }
        }
    }

2. 插入排序

时间复杂度O(N^2)，额外空间复杂度O(1)

public static void insertionSort(int[] arr){
        if(arr == null || arr.length < 2)
            return;
        for(int i = 1; i < arr.length; i ++){
            for(int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--){
                swap(arr, j, j + 1);
            }
        }
    }

3. 选择排序

// 选择排序
	public static void selectSort(int[] arr){
		if(arr == null || arr.length < 2)
			return;
		for(int i = 0; i < arr.length; i ++){
			int minIndex = i;
			for(int j = i; j < arr.length; j ++){
				minIndex = arr[minIndex] < arr[j]? minIndex : j;
			}
			if(i == minIndex)
				continue;
			swap(arr, i, minIndex);
		}
		return;
	}

4. 基数排序

完善中

5. 希尔排序

// 希尔排序
    public static void shellSort2(int[] arr, int gap){
		for(int i = gap; i < arr.length; i ++){
			for(int j =i - gap;j >= 0; j -= gap){
				if(arr[j] > arr[j + gap])
					swap(arr, j, j + gap);
			}
		}
		return;
	}
	// 部分
	public static void shellSort(int[] arr){
		if(arr == null || arr.length < 2){
			return;
		}
		int[] gap = new int[arr.length / 2 + 1];
		int num = 0;
		int len = arr.length;
		while(len > 1){
			gap[num++] = len / 2;
			len /= 2;
		}
		System.out.println(Arrays.toString(gap));
		System.out.println(num);
		for(int i =0; i < num; i++)
			shellSort2(arr, gap[i]);
	}

6. 快速排序（待写）

7. 归并排序（待写）

8. 堆排序（待写）