排序算法

2021-01-13

1 常见的十种排序算法的对比

常用的十种排序算法的对照如下图所示： avatar

常用的排序如快速排序，归并排序，堆排序，冒泡排序等属于比较排序。在排序的最终结果中，元素之间的次序依赖他们之间的比较，每个数都必须和其他数比较，才能确定自己的位置。比较排序的优势是适用于各种规模数据的排序，可以说比较排序适用于一切需要排序的情况。

基数排序、基数排序、桶排序则属于非比较排序，非比较排序是通过确定每个元素之前，应该有多少个元素来排序，针对数组arr，计算arr之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置。非比较排序只要确定每个元素之前的已有元素个数即可，所以一次遍历就可排序完。非比较排序的时间复杂度低，但是由于非比较排序空间复杂度较高，所以对数据规模和数据分布有一定的要求。

1.1 冒泡排序

冒泡排序每一次都比较两个元素，如果顺序错误就交换，遍历数组重复到没有数据需要进行交换，此时数组排序完成。图示如下所示： avatar

package BubbleSort;

/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: ChrisPeng
 * @Date: 2021/01/21/20:17
 * @Description: 冒泡排序
 * 比较相邻的元素，如果第一个比第二个大，就交换两个
 * 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对
 * 针对所有的元素重复以上步骤，除了最后一个
 * 重复步骤，直到排序完成
 */
public class Demo {
    public static void main(String[] args) {
        int[] a = {44,2,4,63,5,6,3,90};
        int[] ints = bubbleSort(a);
        for (int anInt : ints) {
            System.out.printf("%d \n",anInt);
        }
    }
    public static int[] bubbleSort(int[] arr){
        if (arr.length == 0){
            return arr;
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j + 1] < arr[j]){
                    //如果前面的大那么就交换
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
}

1.2 选择排序

选择排序首先在末尾排序序列中找到最小的元素（最大的也行），存放到数组的起始位置，然后再从剩余的未排序的元素中寻找最小元素，放到第二个，以此类推，直到所有的元素已经排序完毕。选择排序的过程如下图所示： avatar

package SelectSort;

/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: ChrisPeng
 * @Date: 2021/01/21/20:35
 * @Description: 选择排序
 * 每一次都将最小的数放在开始的位置处
 */
public class Demo {
    public static void main(String[] args) {
        int[] a = {44,2,4,63,5,6,3,90};
        int[] ints = selectSort(a);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }
    public static int[] selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[j] < arr[min]){
                    min = j;
                }
            }
            //交换最小的与i位置上的数
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
        return arr;
    }
}

1.3 插入排序

插入排序是通过构建有序序列，对于未排序的数据，在已排序的序列中从后向前扫描，找到相应的位置并插入。插入排序的过程如下图所示： avatar

package InsertSort;

/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: ChrisPeng
 * @Date: 2021/01/21/21:02
 * @Description: 插入排序
 * 从第一个元素考试，该元素可以被认作已经排序
 * 取下一个元素，在已经排序的元素中从后向前扫描
 * 如果该元素大于新元素，则将新元素移到下一位置
 * 将新元素插入到该位置后
 * 重复以上步骤
 */
public class Demo {
    public static void main(String[] args) {
        int[] a = {44,2,4,63,5,6,3,90};
        int[] ints = insertSort(a);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }
    public static int[] insertSort(int[] arr){
        int current;
        for (int i = 0; i < arr.length - 1; i++) {
            current = arr[i + 1];
            int preIndex = i;
            while (preIndex >= 0 && current < arr[preIndex]){
                arr[preIndex + 1] = arr[preIndex];
                preIndex --;
            }
            arr[preIndex + 1] = current;
        }
        return  arr;
    }
}

1.4 希尔排序

希尔排序也是一种插入排序，是简单插入排序经过改进之后的一种更高级的版本，也称为缩小增量排序。与插入排序不同的地方在于它会优先比较距离较远的元素。希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

算法描述

选择增量gap = length/2，缩小增量继续以gap = gap / 2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列，希尔排序的增量序列的选择与证明是数学难题。

算法的具体流程如下：

选择一个增量序列t1,t2,...,tk,其中ti > tj,tk = 1;
按增量序列个数k，对序列进行k趟排序;
每趟排序，根据对应的增量ti，将待排序的序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序，仅增量因子为1时，整个序列作为一个表长度即为整个序列的长度。希尔排序的流程图如下图所示：

实现代码如下所示：

package ShellSort;

/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: ChrisPeng
 * @Date: 2021/01/29/22:14
 * @Description: 希尔排序
 */
public class Demo {
    public static void main(String[] args) {
        int[] a = {5,343,56,32,6,633,39343,89};
        int[] ints = ShellSort(a);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }
    public static int[] ShellSort(int[] array) {
        int len = array.length;
        int temp, gap = len / 2;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                temp = array[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && array[preIndex] > temp) {
                    array[preIndex + gap] = array[preIndex];
                    preIndex -= gap;
                }
                array[preIndex + gap] = temp;
            }
            gap /= 2;
        }
        return array;
    }
}

1.5 归并排序

归并排序是建立在归并操作上一种有效的排序算法，该算法采用的是分治算法，将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。算法的步骤如下： * 把长度为n的输入序列分为两个长度为n/2的子序列； * 对这两个子序列分别采用归并排序 * 将两个排序好的子序列合并成一个最终的排序序列

算法流程图示如下所示： avatar

代码实现：

package MergeSort;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: ChrisPeng
 * @Date: 2021/01/29/22:35
 * @Description:
 */
public class Demo {
    public static void main(String[] args) {
        int[] a = {5,343,56,32,6,633,39343,89};
        int[] ints = MergeSort(a);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }
    /**
     * 归并排序
     *
     * @param array
     * @return
     */
    public static int[] MergeSort(int[] array) {
        if (array.length < 2) return array;
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(MergeSort(left), MergeSort(right));
    }
    /**
     * 归并排序——将两段排序好的数组结合成一个排序数组
     *
     * @param left
     * @param right
     * @return
     */
    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length)
                result[index] = right[j++];
            else if (j >= right.length)
                result[index] = left[i++];
            else if (left[i] > right[j])
                result[index] = right[j++];
            else
                result[index] = left[i++];
        }
        return result;
    }
}

1.6 快速排序

快速排序的基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。快速排序实现简单，它原地排序，只需要一个很小的辅助栈，长度为n的数组排序所需要的时间和nlogn成正比 # 实现原理

快速排序使用分治算法来把一个串分为两个子串，具体算法描述如下： * 从数列中挑出一个元素，称为基准； * 重新排序数组，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的数可以放到任一边)。在这个分区退出之后，该基准就处于数列的中间位置。这个是分区操作。 * 递归地把小于基准值的子数列和大于基准值的子数列排序。

流程图如下所示： avatar

快速排序的代码实现如下：

package QuickSort1;

/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: ChrisPeng
 * @Date: 2021/01/31/13:30
 * @Description:
 */
public class Demo {
    public static void main(String[] args) {
        int[] a = {5,343,56,32,6,633,39343,89};
        quickSort(a,0,7);
        for (int i : a) {
            System.out.println(i);
        }
    }
    public static void quickSort(int[] arr,int left,int right){
        if (left > right){
            return;
        }
        //定义保存基准数
        int base = arr[left];
        //定义变量i指向最左边
        int i = left;
        //定义j指向最右边
        int j = right;

        //当i和j不相遇的时候，在循环中进行检索
        while (i != j){
            //j从右向左检索比基准数小的，如果检索到比基准数小的就停下
            //如果检索比基准数大或者相等的的就继续检索
            while (arr[j] >= base && i < j){
                j --;
            }
            //i从左往右检索
            while (arr[i] <= base && i < j){
                i ++;//i从左往右移动
            }
            //走到这i找到了，j找到了，交换i和j的元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        //while条件不成立，说明相遇了
        //相遇了就将基准数和相遇位置的元素
        //先把相遇位置的元素赋值给基准数位置的元素
        arr[left] = arr[i];
        //把基准数赋值给相遇的位置的元素
        arr[i] = base;
        //此时基准数左边的比它小，右边的比它大
        //排基准数的左边
        quickSort(arr,left,i - 1);
        //排基准数的右边
        quickSort(arr,j + 1,right);
    }
}

1.7 堆排序

堆排序是指堆这种数据结构所设计的一种排序算法，堆是一个近似完全二叉树的结构，并且同时满足堆积的性质，即子结点的键值或索引总是小于或者大于它的父节点。一般升序采用大顶堆，降序采用小顶堆。

算法流程

将无序序列构建成一个堆，根据升序降序需求选择大顶堆或者小顶堆，大顶堆是结点大于叶子结点的数据，大顶堆用于升序排序，小顶堆用于降序排序。
将堆顶元素与末尾交换，将最大元素沉到数组末尾
重新调整结构，使其满足堆的定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

排序的过程如下图所示： avatar

代码实现：

import java.lang.reflect.Array;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: ChrisPeng
 * @Date: 2021/01/29/13:55
 * @Description: 堆排序
 */
public class HeapSort {
    public static void main(String[] args) {
        /**
         * 升序大顶堆，降序小顶堆
         */
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int)(Math.random()*8000000);
        }
        System.out.println("排序前");
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String data1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间是="+data1Str);
        heapSort(arr);
        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间是="+date2Str);
    }
    public static void heapSort(int arr[]){
        int temp = 0;
        System.out.println("堆排序");
        //第一步：将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr,i,arr.length);
        }
        //第二步：将堆顶元素与末尾元素交换，将最大元素沉到数组末端
        //第三步：重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序
        for (int j = arr.length - 1; j > 0 ; j--) {
            //交换
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr,0,j);//总是从顶上开始
        }
//        System.out.println("数组=" + Arrays.toString(arr));
    }
    //将一个数组（二叉树）调整成一个大顶堆

    /**
     * 功能： 完成将以i对应的非叶子结点的数调整成大顶堆
     * @param arr 待调整的数组
     * @param i 表示非叶子结点在数组中的索引
     * @param length 表示对多少个元素进行继续调整，length是在逐渐减少的
     */
    public static void adjustHeap(int arr[],int i,int length){
        int temp = arr[i];//取出当前元素的值，保存在临时变量中
        //开始调整
        //j = i * 2 + 1指向的是i结点的左子节点
        for (int j = i * 2 + 1; j < length; j = j * 2 + 1) {
            if (j + 1 < length && arr[j] < arr[j + 1]){
                //说明左子节点小于右子结点的值
                j++;//j指向右子结点
            }
            if (arr[j] > temp){
                //如果子结点大于父节点
                arr[i] = arr[j];
                i = j;//把较大的值赋给当前的结点，然后让i指向k，继续循环比较
            }else {
                break;
            }
        }
        //for循环结束后，已经将以i为父节点的树的最大值放在了最顶
        arr[i] = temp;//将temp值放到调整后的位置
    }

}