七种排序算法

当n较大时，则应采用时间复杂度为O(nlogn)的排序算法：快速排序、堆排序、归并排序。

常见的排序算法有：

• 插入排序（直接插入、希尔排序）
• 选择排序（简单选择、堆排序）
• 交换排序（冒泡排序、快速排序）
• 归并排序

当n较大时，则应选择时间复杂度为O(nlogn)的排序算法：快速排序、堆排序、归并排序
快速排序是目前基于比较的内部排序中被认为最好的方法，当待排的关键字是随机分布时，快速排序的平均时间最短
如果大体有序的话，可以选择插入排序。

插入排序：

public static void insertSort(int[] arr){
    //存放待插入元素
    int temp;
    for (int i = 1; i < arr.length; i++){
        temp = arr[i];
        int j;
        for (j = i - 1; j >= 0; j--){
            //如果符合条件就往后移位，为当前元素腾出空间
            if (arr[j] > temp){
                arr[j + 1] = arr[i];
            } else {
                break;
            }
        }
        arr[j + 1] = temp;
    }
}

希尔排序：
基于插入排序的思想，缩小增量排序（直接插入的改进版）

public static void shellSort(int[] arr){
    //获取数组长度，确定增量gap
    int len = arr.length;
    int gap = len / 2;
    int tmp;
    
    while(gap > 0){
        for(int i = gap; i < len; i++){
            tmp = arr[i];
            //获取前一个元素的索引
            int preIndex = i - gap;
            while(preIndex >= 0 && arr[preIndex] > tmp){
                arr[preIndex + gap] = arr[preIndex];
                preIndex -= gap;
            }
            arr[preIndex + gap] = tmp;
        }
        gap /= 2;
    }
}

选择排序：

public static void selectSrot(int[] arr){
    int tmp;
    for(int i = 0; i < arr.length; i++){
        for(int j = j + 1; j < arr.length; j++){
            if (arr[i] > arr[j]){
                swap;
            }
        }
    }
} 

堆排序：
借助完全二叉树进行排序，将数据构建成大根堆或者小根堆，然后将顶点的元素和最后的元素互换，然后继续构建大根堆的过程。
设一个节点为R[i]，则左孩子节点为R[2 * i + 1]，右孩子为R[2 * i + 2]
最后一个非叶子节点为R[(len - 1) / 2]

public static void heapSort(int[] arr){
    //循环建立初始堆
    for(int i = (arr.length - 1) / 2; i >= 0; i--){
        headAdjust(arr, i, arr.length);
    }
    
    //进行n - 1次循环，完成排序
    for(int i = arr.length - 1; i--){
        //最后一个元素和第一个元素交换
        int tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;
        
        //然后将将除最后一个元素继续构建大根堆
        headAdjust(arr, 0, i);
    }
}

public static void headAdjust(int[] arr, int parent; int len){
    //保存当前父节点
    int tmp = arr[parent];
    int child = parent * 2 + 1;
    
    while(child < len){
        //判断是否有右孩子，并且右孩子的值大于左孩子的值，则选择右孩子
        if (child + 1 < len && arr[child] < arr[child + 1]){
            child++;
        }
        //如果父节点的值大于孩子节点的值，则直接退出
        if (tmp >= arr[child]){
            break;
        }
        
        //把孩子节点的值赋值给父节点
        arr[parent] = arr[child];
        arr[child] = tmp;
    }
}

冒泡排序：

public static void bubbleSort(int[] arr){
    int tmp;
    for(int i = 1; i < arr.length; i++){
        for(int j = 0; j <= arr.length - 1 - i; j++){
            if (arr[j] > arr[j + 1]){
                swap;
            }
        }
    }
}

快速排序：
选取第一个元素作为基准元素，两端各设两个哨兵，右边移动到小于基准元素时停止，左边开始移动，直至遇到大于基准元素时停止，然后两元素交换，重复次过程，直至两哨兵相遇，将基准元素和相遇的值进行交换，此时基准元素左边的元素均小于基准元素，基准元素右边的值均大于基准元素，然后将基准元素左右两端的元素重复此过程，直至完全有序。

public static void quickSort(int left, int right){
    int i, j, t, tmp;
    if(left > right){
        return;
    }
    
    //基准元素
    tmp = arr[left];
    //左哨兵
    i = left;
    //右哨兵
    j = right;
    
    //顺序很重要，要先从左边开始
    while(i != j){
        while(arr[j] > tmp && i > j){
            j--;
        }
        while(arr[i] < tmp && i > j){
            i++;
        }
        if(i < j){
            t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
    //最终将基准元素归位
    arr[left] = arr[i];
    arr[i] = tmp;
    quickSort(left, i - 1);
    quickSort(i + 1, right);
}

归并排序：

public static void mergeSort(int[] arr, int left, int right){
    int mid = (right + left) / 2;
    if (left < right){
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

public static void merge(int[] arr, int left, int mid, int right){
    //创建一个临时数组用于存放排序的数据
    int[] tmp = 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]){
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }
    //将左边或右边剩余的元素添加到临时数组中
    while(i <= mid){
        tmp[k++] = arr[i++];
    }
    while(j <= right){
        tmp[k++] = arr[j++];
    }
    
    //将临时数组添加到原数组中
    k = 0;
    while(left <= right){
        arr[left++] = tmp[k++];
    }
}