初级篇：三个O(n^2)的排序算法

仅记录代码实现和大概思路。

一、冒泡

思路：内层循环每次都从后面开始，外层从前面开始。内层每次都会找到一个小的数，放在数组的最前面。因此内层循环i次就完成了排序。

    public void BubbleSort(int[] arr){
        int temp=0;//临时变量
        for(int i=0; i<arr.length-1; i++){   //表示趟数，一共arr.length-1次。
            for(int j=arr.length-1; j>i; j--){
                if(arr[j] < arr[j-1]){
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }
    }

二、选择排序

以如下代码为例，选择排序就是，每次都找到未排序的最小的元素，用一个变量记录这个元素索引，然后将该元素和未排序的部分的首位元素交换，可以看到交换次数只有n次。

    public static void select_sort(int array[]){
        for(int i=0;i<array.length-1;i++){
            int minIndex = i;
            for(int j=i+1;j<array.length;j++){
                if(array[j]<array[minIndex]){
                    minIndex = j;
                }
            }
            if(minIndex != i){
                int temp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = temp;
            }
        }
    }

三、插入排序

类似于打扑克牌的时候，让摸到的手牌一直有序。

    public static void  insert_sort(int array[]){
        int temp = array[0];
        for(int i=0;i<array.length-1;i++){
            for(int j=i+1;j>0;j--){
                if(array[j] < array[j-1]){
                    temp = array[j-1];
                    array[j-1] = array[j];
                    array[j] = temp;
                }else{         //不需要交换 提前退出是优化
                    break;
                }
            }
        }
    }

高级篇：三个O(nlogn)的排序算法

四、归并排序

public class MergeSort {
    public void MergeSort(int[] arr) {
        MergeSort(arr,0,arr.length-1);
    }

    private void MergeSort(int[] arr, int left, int right) {
        // 如果 left == right，表示数组只有一个元素，则不用递归排序
        if (left < right) {
            // 把大的数组分隔成两个数组
            int mid = (left + right) / 2;
            // 对左半部分进行排序
            MergeSort(arr, left, mid);
            // 对右半部分进行排序
            MergeSort(arr, mid + 1, right);
            //进行合并
            merge(arr, left, mid, right);
        }
    }

    private void merge(int[] arr, int left, int mid, int right) {
//先用一个临时数组把他们合并汇总起来
        int[] array = new int[right - left + 1];
        int i = left;//左半部分起始索引
        int j = mid + 1;//右半部份起始索引
        int k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                array[k++] = arr[i++];
            } else {
                array[k++] = arr[j++];
            }
        }
        while(i <= mid)
            array[k++] = arr[i++];
        while(j <= right)
            array[k++] = arr[j++];
        // 把临时数组复制到原数组
        for (i = 0; i < k; i++) {
            arr[left] = array[i];
            left++;
        }
    }
}

五、快速排序

快速排序有三个版本，下列为初级版本，版本2应该是使用随机数，版本3是三路快排，可以理解成分成三个部分，左边是小于，中间是等于，右边是大于。（暂时收录基本写法）

public class QuickSort {
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int n[], int left, int right) {
        int dp;
        if (left < right) {
            dp = partition(n, left, right);//先找一个数，然后分成两边处理
            quickSort(n, left, dp - 1);
            quickSort(n, dp + 1, right);
        }
    }
    //partiton是最核心的部分，目的是对于某个数a，其左边都是小于a，右边都是大于a。
    public static int partition(int n[], int left, int right) {
        int pivot = n[left];//这里选择的是最左侧，也是最基础的写法，这里使用随机数可以优化

        while (left < right) {
            while (left < right && n[right] >= pivot)
                right--;
            if (left < right) {
                n[left] = n[right];
                left++;
            }
            while (left < right && n[left] <= pivot)
                left++;
            if (left < right) {
                n[right] = n[left];
                right--;
            }
        }
        n[left] = pivot;
        return left;
    }
}

六、堆排序

堆排序的一个细节是，如果给定的是一个接一个的数据，那么慢慢插入，如果是给定了一个数组过来，则最好直接heapify调整。对应本示例的downAdjust方法。

大顶堆：每个结点的值都大于或等于其左右孩子结点的值
小顶堆：每个结点的值都小于或等于其左右孩子结点的值

public class HeapSort {
    // 堆排序
    public static int[] heapSort(int[] arr) {
        int n = arr.length;
        //构建大顶堆
        for (int i = (n - 2) / 2; i >= 0; i--) {
            downAdjust(arr, i, n - 1);
        }
        //进行堆排序
        for (int i = n - 1; i >= 1; i--) {
            // 把堆顶元素与最后一个元素交换
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            // 把打乱的堆进行调整，恢复堆的特性
            downAdjust(arr, 0, i - 1);
        }
        return arr;
    }

    //下沉操作。在parent到n这个区间，parent这个位置的数不对。
    public static void downAdjust(int[] arr, int parent, int n) {
        //临时保存要下沉的元素
        int temp = arr[parent];
        //定位左孩子节点的位置
        int child = 2 * parent + 1;
        //开始下沉
        while (child <= n) {
            // 如果右孩子节点比左孩子大，则定位到右孩子
            if(child + 1 <= n && arr[child] < arr[child + 1])
                child++;
            // 如果孩子节点小于或等于父节点，则下沉结束
            if (arr[child] <= temp ) break;
            // 父节点进行下沉
            arr[parent] = arr[child];
            parent = child;
            child = 2 * parent + 1;
        }
        arr[parent] = temp;
    }
}

二分查找法

public class Find {
    public int binarysearch(int a[], int key) {
        int low = 0;
        int high = a.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (a[mid] > key)
                high = mid - 1;
            else if (a[mid] < key)
                low = mid + 1;
            else if (a[mid] == key)
                return mid;
        }
        return -1;
    }
}

又或者是

public class Find {
    public int binarysearch(int a[], int key) {
        int low = 0;
        int high = a.length ;//两个写法的边界是不同的
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (a[mid] > key)
                high = mid ;
            else if (a[mid] < key)
                low = mid + 1;
            else if (a[mid] == key)
                return mid;
        }
        return -1;
    }
}