十大排序算法实现

待更新，未完待续......

import java.util.Arrays;

public class Sort {
	public static void main(String[] args) {
		int[] arr = new int[] { 5, 4, 3, 2, 1, 0 };

		bubbleSort(arr);
		for (int val : arr) {
			System.out.print(val + " ");
		}

		System.out.println();

		selectionSort(arr);
		for (int val : arr) {
			System.out.print(val + " ");
		}

		System.out.println();

		insertSort(arr);
		for (int val : arr) {
			System.out.print(val + " ");
		}

		System.out.println();

		shellSort(arr);
		for (int val : arr) {
			System.out.print(val + " ");
		}
		
		System.out.println();
		
		int[] mergeArr = mergeSort(arr);
		for (int val : mergeArr) {
			System.out.print(val + " ");
		}
	}

	
	public static void bubbleSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) { // arr.length - 1个元素都要冒泡一下: 当arr.length - 1个元素都排好序了，最后一个也就排好了
			boolean flag = true;// 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成

			for (int j = 0; j < arr.length - 1 - i; j++) { // 当前元素arr[j]需要和(arr.length - 1 - i)个元素比较
				if (arr[j] > arr[j + 1]) {
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;

					flag = false;
				}
			}

			if (flag) {
				break;
			}
		}
	}

	
	public static void selectionSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) { // 未排序序列一共有arr.length - 1个
			int minIndex = i; // 记录每次未排序序列中最小值的索引位置
			for (int j = i + 1; j < arr.length; j++) {
				minIndex = arr[minIndex] > arr[j] ? j : minIndex;
			}
			if (minIndex != i) {
				int temp = arr[minIndex];
				arr[minIndex] = arr[i];
				arr[i] = temp;
			}
		}
	}

	
	public static void insertSort(int[] arr) {
		for (int i = 1; i < arr.length; i++) { // 未排序
			int temp = arr[i]; // 当前待插入元素

			int insertIndex = i;
			for (int j = i - 1; j >= 0; j--) { // 已排序
				if (arr[j] > temp) {
					arr[j + 1] = arr[j];
					insertIndex = j;
				} else {
					break;
				}
			}
			arr[insertIndex] = temp;
		}
	}

	
	public static void shellSort(int[] arr) {
		int length = arr.length;
		for (int step = length / 2; step >= 1; step = step / 2) { // 根据初始增量和每次减少的增量，最后的增量为1时进行的是插入排序
			for (int i = step; i < length; i++) { // 未排序
				int temp = arr[i];

				int insertIndex = i;
				for (int j = i - step; j >= 0; j = j - step) { // 已排序
					if (arr[j] > temp) {
						arr[j + step] = arr[j];
						insertIndex = j;
					} else {
						break;
					}
				}
				arr[insertIndex] = temp;
			}
		}
	}

	public static int[] mergeSort(int[] arr) {
		if (arr.length == 1) {
			return arr;
		}

		int middle = arr.length / 2;
		int[] left = Arrays.copyOfRange(arr, 0, middle);
		int[] right = Arrays.copyOfRange(arr, middle, arr.length);
		int[] leftVal = mergeSort(left);
		int[] rightVal = mergeSort(right);

		return merge(leftVal, rightVal);
	}
	public static int[] merge(int[] left, int[] right) {
		int[] result = new int[left.length + right.length];
		int k = 0;// result数组的指针
		int i = 0;// left数组指针
		int j = 0;// right数组指针
		
		while(i < left.length && j < right.length){
            if(left[i] < right[j]){
                result[k] = left[i];
                i++;
            }else{
                result[k] = right[j];
                j++;
            }
            k++;
        }
        //将剩下的直接全部移过去
        while(i < left.length){
            result[k] = left[i];
            i++;
            k++;
        }

        while (j < right.length){
            result[k] = right[j];
            j++;
            k++;
        }

        return result;//result已经是排好序的
	}

	public static void quickSort(int[] arr) {

	}

	public static void heapSort(int[] arr) {

	}

	public static void countingSort() {

	}

	public static void bucketSort() {

	}

	public static void radixSort() {

	}
}