[JAVA]排序

目录

排序算法复杂度及稳定性分析

1.冒泡排序

2.选择排序

3.插入排序

直接插入排序代码

二分法插入排序代码

4.快速排序

5.归并排序 

6.堆排序

7.希尔排序

8.桶排序

题目描述：定一个长度为 n 的数组，请你编写一个函数，返回该数组按升序排序后的结果。

排序算法复杂度及稳定性分析

1.冒泡排序

首先拿第一个元素和后面的所有一个个比较，如果比后面的大就交换，所以始终会保证第一个元素是最小的，然后再从第二个第三个，以此类推，swap方法表示交换两个数字的值。

    public int[] MySort (int[] arr) {
        for(int i = 0;i < arr.length - 1;i++){
            for(int j = i + 1;j < arr.length;j++){
                if(arr[i] > arr[j]){
                    swap(arr,i,j);
                }
            }
        }
        return arr;
    }
    public static void swap(int[] arr,int i,int j){
        if(i != j){
            int num = arr[i];
            arr[i] = arr[j];
            arr[j] = num;
        }
    }

我们看到每次循环的时候j都是从0开始的，并且是相邻两个元素的比较，所以第一轮比完了之后会把最大的值放到数组的最后，第二轮的时候会把第二大的值放到数组的倒数第二个位置，以此类推。他和上一个的区别是，上一个每次循环都是把小的往前排，而这个每次循环都是把大的往后排。也可以把for改为while循环。

    public int[] MySort (int[] arr) {
        int  count = arr.length - 1;
        while(count > 0){
            for(int i = 0;i < count;i++){
                if(arr[i] > arr[i + 1]){
                    swap(arr,i,i + 1);
                }
            }
            count--;
        }
        return arr;
    }
    public static void swap(int[] arr,int i,int j){
            int num = arr[i];
            arr[i] = arr[j];
            arr[j] = num;
    }

2.选择排序

选择排序和冒泡排序有一点点像，选择排序是默认前面都是已经排序好的，然后从后面选择最小的放在前面排序好的的后面，首先第一轮循环的时候默认的排序好的为空，然后从后面选择最小的放到数组的第一个位置，第二轮循环的时候默认第一个元素是已经排序好的，然后从剩下的找出最小的放到数组的第二个位置，第三轮循环的时候默认前两个都是已经排序好的，然后再从剩下的选择一个最小的放到数组的第三个位置，以此类推。

    public int[] MySort (int[] arr) {
        for(int i = 0;i < arr.length;i++){
            int count = i;
            for(int j = i + 1;j < arr.length;j++){
                if(arr[count] > arr[j]){
                    count = j;
                }
            }
            if(i != count){
                swap(arr,i,count);
            }
        }
        return arr;
    }
    public static void swap(int[] arr,int i,int count){
            int num = arr[i];
            arr[i] = arr[count];
            arr[count] = num;
    }

3.插入排序

插入排序的原理是默认前面的元素都是已经排序好的，然后从后面逐个读取插入到前面排序好的合适的位置，就相当于打扑克的时候每获取一张牌的时候就插入到合适的位置一样。插入排序可以分为两种，一种是直接插入还一种是二分法插入，直接插入的原理比较简单，就是往前逐个查找直到找到合适的位置然后插入，二分法插入是先折半查找，找到合适的位置然后再插入。

直接插入排序代码

    public int[] MySort (int[] arr) {
        for(int i = 0;i < arr.length;i++){
            int j = i;
            int count = arr[i];
            for(;j > 0;j--){
                if(arr[j - 1] > count){
                    arr[j] = arr[j - 1];
                }else{
                    break;
                }
            }
            arr[j] = count;
        }
        return arr;
    }

二分法插入排序代码

    public int[] MySort (int[] arr) {
        for(int i = 1;i < arr.length;i++){
            if(arr[i - 1] > arr[i]){
                int key = arr[i];
                int low = 0;
                int hight = i - 1;
                while(low <= hight){
                    int mid = (low + hight) >> 1; //右移一位，相当于除以2，但右移的运算速度更快                                           
                                                  //若使用(low+high)/2求中间位置容易溢出
                    if(arr[mid] > key){
                        hight = mid - 1;
                    }else{
                        low = mid + 1;
                    }
                }
                for(int j = i;j > low;j--){            
                    arr[j] = arr[j - 1];
                }
                arr[low] = key;
            }
        }
        return arr;
    }

4.快速排序

快速排序原理是首先要找到一个中枢，把小于中枢的值放到他前面，大于中枢的值放到他的右边，然后再以此方法对这两部分数据分别进行快速排序。

    public int[] MySort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
        return arr;
    }
    private void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int key = arr[start];//用待排数组的第一个作为中枢
            int i = start;
            for (int j = start + 1; j <= end; j++) {
                if (key > arr[j]) {
                    swap(arr, j, ++i);
                }
            }
            arr[start] = arr[i];//先挪，然后再把中枢放到指定位置
            arr[i] = key;
            quickSort(arr, start, i - 1);
            quickSort(arr, i + 1, end);
        }
    }
    public static void swap(int[] arr,int i,int j){
        if(i != j){
            int num = arr[i];
            arr[i] = arr[j];
            arr[j] = num;
        }
    }

5.归并排序 

归并排序是把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。（先把待排序列分为两部分，然后各部分再分为两部分，一直分下去，直到不能再分为止，然后在两两合并两个有序数组，直到合并完为止。）

public int[] MySort(int[] arr) {
    int i = 1;
    while (i < arr.length) {
        //原理很简单，就是先两个两个合并，然后4个，然后8个……
        for (int j = 0; j + i < arr.length; j += 2 * i) {
            merge(arr, j, j + i - 1, Math.min(j + 2 * i - 1, arr.length - 1));
        }
        i = i << 1;
    }
    return arr;
}
 
private void merge(int[] data, int left, int center, int right) {
    int length = right - left + 1;
    int[] tmp = new int[length];
    int tempIndex = 0;
    //_left是前半部分开始的位置，_right是后半部分开始的位置
    int _left = left;
    int _right = center + 1;
    while (_left <= center && _right <= right) {
        if (data[_left] <= data[_right]) {
            tmp[tempIndex++] = data[_left++];
        } else {
            tmp[tempIndex++] = data[_right++];
        }
    }
    while (_right <= right) {
        tmp[tempIndex++] = data[_right++];
    }
    while (_left <= center) {
        tmp[tempIndex++] = data[_left++];
    }
    tempIndex = 0;
    while (tempIndex < length) {
        data[left + tempIndex] = tmp[tempIndex++];
    }
}

6.堆排序

堆排序，也可以理解为二叉树排序，这里的堆分为两种，一种是大顶堆，一种是小顶堆，我们所有的排序方法都以升序为主，其实倒序原理也都差不多，所以这里我们主要分析的是大顶堆。

    public int[] MySort (int[] arr) {
        int length = arr.length;
        buildMaxHeap(arr, length);
        for (int i = 0; i < length; i++) {
            swap(arr, 0, length - 1 - i);
            maxHeapfy(arr, 0, length - i - 1);
        }
        return arr;
    }
 
    private void maxHeapfy(int[] arr, int i, int heapSize) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int largest = i;
        if (left < heapSize && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < heapSize && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest != i) {//把最大值给父节点
            swap(arr, largest, i);
            maxHeapfy(arr, largest, heapSize);
        }
    }
 
    private void buildMaxHeap(int[] array, int heapSize) {
        //从最后一个非叶子节点开始循环
        for (int i = (heapSize - 2) >> 1; i >= 0; i--) {
            maxHeapfy(array, i, heapSize);
        }
    }
    
    public static void swap(int[] arr,int i,int j){
        int num = arr[i];
        arr[i] = arr[j];
        arr[j] = num;
    }

7.希尔排序

希尔排序也成缩小增量排序，原理是将待排序列划分为若干组，每组都是不连续的，有间隔step，step可以自己定，但间隔step最后的值一定是1，也就说最后一步是前后两两比较。间隔为step的默认划分为一组，先在每一组内进行排序，以使整个序列基本有序，然后再减小间隔step的值，重新分组再排序……不断重复，直到间隔step小于1则停止。

    public int[] MySort (int[] arr) {
        int key = arr.length >> 1;
        while(key >= 1){
            for(int i = key;i < arr.length;i++){
                for(int j = i;j >= key;j -= key){
                    if(arr[j] < arr[j - key]){
                        swap(arr,j,j - key);
                    }else{
                        //如果大于，就不用继续往前比较了，因为前面的元素已经排好序了
                        break;
                    }
                }  
            }
            key >>= 1;
        }
        return arr;
    }
    public static void swap(int[] arr,int i,int j){
        int num = arr[i];
        arr[i] = arr[j];
        arr[j] = num;
    }

8.桶排序

桶排序是将数组分散到有限的桶中，然后每个桶再分别排序，而每个桶的排序又可以使用其他排序方式进行排序，可以是桶排序也可以是其他排序。桶的大小可以随便定，如果桶的数量足够多就会变成我们后面介绍的计数排序，其实我们完全可以把桶固定在一个数量，根据数组的大小来确定，也可以自己定，比如3个或者5个7个等，桶的大小确定之后，下一步就需要把数组中的值一一存放到桶里，小的值就会放到前面的桶里，大的值就会放到后面的桶里，中间的值就会放到中间的桶里，然后再分别对每个桶进行单独排序，最后再把所有桶的数据都合并到一起就会得到排序好的数组。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()){
            int n = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = in.nextInt();
            }
            bucketSort(arr,3);
            System.out.println(Arrays.toString(arr));
        }
    }
    public static void bucketSort(int[] arr,int bucketSize){
        int max = arr[0];
        int min = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }else if (arr[i] < min) {
                min = arr[i];
            }
        }
        //bucketSize表示每个桶存放数据的大小，count表示总共桶的数量
        int count = (max - min) / bucketSize + 1;
        ArrayList<ArrayList<Integer>> bucket = new ArrayList<>(count);
        for (int i = 0; i < count; i++) {
            //根据value的大小存放到不同的桶里，最终的结果是小的出现在前面的桶里，大的出现在最后的桶里，
            //中间的也出现在中间的桶里了，然后再对每个桶进行排序
            bucket.add(new ArrayList<>());
        }
        for (int i = 0; i < arr.length; i++) {
            bucket.get((arr[i] - min) / bucketSize).add(arr[i]);
        }
 
        int index = 0;
        for (int i = 0; i < bucket.size(); i++) {
            //取出每个桶的数据
            Integer[] array = new Integer[bucket.get(i).size()];
            array = bucket.get(i).toArray(array);
            //每一个桶进行排序，这里面可以选择其他排序算法进行排序
            Arrays.sort(array);
            for (int j = 0; j < array.length; j++) {
                arr[index++] = array[j];
            }
        }
    }
}