[数据结构与算法]算法-八大排序

算法-八大排序

冒泡排序（Bubble Sort）

原理

冒泡排序是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的数组，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

图解

代码实现

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {
        Integer[] arr = {4, 3, 5, 6, 1, 7, 0, 2};
        bubbleSort(arr);
        System.out.println(Arrays.asList(arr));
    }

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

稳定性

冒泡排序是不稳定的

时间复杂度

冒泡排序的时间为 O(n^2)

选择排序（Selection sort）

原理

选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

图解

代码实现

import java.util.Arrays;

/**
 * 选择排序
 */
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {4, 3, 5, 6, 1, 7, 0, 2};
        SelectSort(arr);
        System.out.println(Arrays.asList(arr));
    }
    public static void SelectSort(int[] arr) {
        //选择一个辅助变量
        int tmp;
        for (int i = 0; i < arr.length; i++) {
            int min = arr[i];
            for(int j = i ; j<arr.length;j++){
                if(arr[j]<min){
                    tmp = min;
                    min =arr[j];
                    arr[j] = tmp;
                }
            }
            arr[i] = min;
        }
    }
}

稳定性

选择排序是不稳定的

时间复杂度

选择排序的时间为 O(n^2)

直接插入排序（Insert sort）

原理

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 。

图解

代码实现

import java.util.Arrays;

/**
 * 直接插入排序
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {4, 3, 5, 6, 1, 7, 0, 2};
        insertSort(arr);
        System.out.println(Arrays.asList(arr));
    }
    public static void insertSort(int[] arr){
        //辅助变量
        int tmp ;
        for(int i = 1;i<arr.length;i++){
            tmp = arr[i];
            int j;
            for(j = i-1;j>=0;j--){
                //已排序数组从后往前依次和当前数对比
                if(arr[j]>tmp){
                    //如果已排序数大于，就将已排序数往后移一位
                    arr[j+1]=arr[j];
                }else{
                    //如果已经小于，就停止循环
                    break;
                }
            }
            //将当前数存储到当前已经对比完的位置
            arr[j+1] = tmp;
        }
    }
}

稳定性

直接插入排序是稳定的

时间复杂度

直接插入排序的时间为 O(n^2)

希尔排序（Shell sort）

原理

希尔排序是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

图解

代码实现

import java.util.Arrays;

/**
 * 希尔排序
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {4, 3, 5, 6, 1, 7, 0, 2};
        shellSort(arr);
        System.out.println(Arrays.asList(arr));
    }

    public static void swap(int[] arr, int x, int y) {
        //辅助交换变量
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }

    public static void shellSort(int[] arr) {
        //获取一个增量间隔
        int interval = (int) Math.floor(arr.length / 2);
        //开始遍历
        while (interval>=1){
            for(int i = interval ; i<arr.length;i++){
                int j = i;
                while (j-interval>=0){
                    if(arr[j]<arr[j-interval]){
                        swap(arr,j,j-interval);
                    }
                    j-=interval;
                }
            }
            interval = (int)Math.floor(interval/2);
        }
    }
}

堆排序（Heap sort）

原理

堆排序是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。

• 完全二叉树：除了最后一层之外的其他每一层都被完全填充，每一层从左到右的填充数据，不能空缺。
• 大根堆：任意一个节点的值均大于等于它的左右孩子的值，位于堆顶的节点值最大。
• 小根堆：任意一个节点的值均小于等于它的左右孩子的值，位于堆顶的节点值最小。

实现流程

• 假设当前节点的下标为i，那么它的父亲节点为(i-1)/2，每次调整的时候就把调整进来的节点与它的父亲节点进行比较，比它的父节点大就交换，一直重复调整
• 每次把堆顶的节点放到最后，然后堆大小减1，然后调整为大根堆，一直重复，直到大根堆的大小为0为止

图解

代码实现

import java.util.Arrays;

/**
 * 堆排序
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {4, 3, 5, 6, 1, 7, 0, 2};
        int size = arr.length;
        while (size>0){
            for(int i = 0;i<size;i++){
                heapify(arr,i);
            }
            heapSort(arr,size-1);
            size--;
        }
        System.out.println(Arrays.asList(arr));
    }
    public static void swap(int[] arr, int x, int y) {
        //辅助交换变量
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }
    /**
     * @param arr 数组
     * @param i   需要维护的节点
     */
    public static void heapify(int[] arr,  int i) {
            //子节点是否大于父节点
            while (arr[i]>arr[(i-1)/2]){
                //是就进行交换
                swap(arr,i,(i-1)/2);
                //最重要的一步，回头判断和父节点的大小
                i = (i-1)/2;
            }
    }
    /**
     *
     * @param arr 数组
     * @param i 数组剩余未排序长度
     */
    public static  void heapSort(int[] arr , int i){
        //如果剩余未排序长度大于1，将第一个元素和最后一个元素调换位置，
        swap(arr,0,i);

    }
}

快速排序（Quick sort）

原理

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

实现流程

1. 首先设定一个分界值，通过该分界值将数组分成左右两部分。
2. 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

图解

代码实现

import java.util.Arrays;

/**
 * 快速排序
 */
public class Quicksort {
    public static void main(String[] args) {
        int[] arr = {4, 3, 5, 6, 1, 7, 0, 2};
        quicksort(arr, 0, arr.length - 1);
        System.out.println(Arrays.asList(arr));
    }

    public static void swap(int[] arr, int x, int y) {
        //辅助交换变量
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }

    public static void quicksort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        //基准
        int pivot = arr[right];
        //辅助指针
        int l = left;
        int r = right - 1;
		//循环遍历
        while (l < r) {
            while (l < r && arr[l] <= pivot) {
                l++;
            }
            while (l < r && arr[r] >= pivot) {
                r--;
            }
            swap(arr, l, r);
        }
        //将中间位与末尾进行交换，这样，基准就找到了自己合适的位置
        if (arr[l] >= arr[right]) {
            swap(arr, l, right);
        } else {
            l++;
        }
		//左半边
        quicksort(arr, left, l - 1);
        //右半边
        quicksort(arr, l + 1, right);
    }
}

归并排序（Merge Sort）

原理

归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

实现流程

1. 将需要排序的序列两两划分进行第一次组内排序。
2. 将第一步排好的组再次两两组合进行组内排序。
3. 重复以上步骤，直至最后一次排序完成。

图解

代码实现

/**
 * 归并
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {4, 3, 5, 6, 1, 7, 0, 2};
        //创建一个新的数组去辅助存值
        int[] tmp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, tmp);
        System.out.println(arr);
    }
    //归并
    private static void mergeSort(int[] arr, int first, int last, int[] tmp) {
        if (first >= last) {
            return;
        }
        //分割点
        int mid = (first + last) / 2;
        //前半部分继续归并
        mergeSort(arr, first, mid, tmp);
        mergeSort(arr, mid + 1, last, tmp);
        //合并
        mergeArray(arr, first, mid, last, tmp);
    }
    //合并
    private static void mergeArray(int[] arr, int first, int mid, int last, int[] tmp) {
        //给左边第一个数组添加一个辅助指针
        int poi_l = first;
        //给右边第一个数组添加一个辅助指针
        int poi_r = mid + 1;
        //给辅助数组一个辅助指针
        int poi_t = 0;
        while (poi_l <= mid && poi_r <= last) {
            if (arr[poi_l] < arr[poi_r]) {
                tmp[poi_t++] = arr[poi_l++];
            } else {
                tmp[poi_t++] = arr[poi_r++];
            }
        }
        //右边数组已经是最后一个元素了
        while (poi_l <= mid) {
            tmp[poi_t++] = arr[poi_l++];
        }
        //左边数组已经是最后一个元素了
        while (poi_r <= last) {
            tmp[poi_t++] = arr[poi_r++];
        }
        //将辅助数组的值移交给之前数组
        for (int i = 0; i < poi_t; i++) {
            arr[first + i] = tmp[i];
        }
    }
}

基数排序（Radix sort）

还在继续学习中