数据结构之排序算法_排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部

基本介绍

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序的过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序、基数排序等。用一张图概括：

 

关于时间复杂度：

 

 

 

 

 

 

 

 

 

 

关于稳定性：

1、稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

2、不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

一、直接插入排序

概念：插入排序类似于打扑克调整牌序，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

1、算法步骤：

（1）将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

（2）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

（3）至于如何插入有序序列，先将待插入元素保存在一个变量中，然后从右到左（这就是为什么j--的原因）依次跟有序序列进行比较，如果比较到有序序列中的某一个元素比待插入元素小，则将它放在它前面。

2、代码实现

package cn.wyu.sort;
 
/**
 * @author linwillen
 * @create 2020-04-21-23:40
 */
public class InsertSort {
 
    public static void main(String[] args) {
        int[] array = {2,3,5,1,23,6,78,34,23};
        //insertSort(array);
        insertSort2(array);
        System.out.println(Arrays.toString(array));//1 2 3 5 6 23 23 34 78
 
    }
 
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            for (int j = i;j > 0;j--){//有点像冒泡排序，将小的值往前交换
                if(array[j]<array[j - 1]){
                    int temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                }
            }
        }
    }
    //优化方案
    public static void insertSort2(int[] array){
 
        for(int i=1; i<array.length; i++){
            int temp = array[i];//保存每次需要插入的那个数
            int j;
            for(j=i; j>0 && array[j-1]>temp; j--){//这个较上面有一定的优化
                array[j] = array[j-1];//把大于需要插入的数往后移动。最后不大于temp的数就空出来j
            }
            array[j] = temp;//将需要插入的数放入这个位置
        }
 
    }
}

二、希尔排序

1、算法步骤：在此我们选择增量 gap = length / 2，缩小增量继续以 gap = gap / 2 的方式，这种增量选择我们可以用一个序列来表示，{n / 2, (n / 2) / 2 ... 1}，称为增量序列。假设n=20，则序列为{10，5，2，1}，10表示将20个元素分为10组，每组2个元素，每个元素之间的增量为10。5表示将20个元素分为5组，每组4个元素，每个元素之间的增量为5。2表示将20个元素分为2组，每组10个元素，每个元素之间的增量2。1表示将20个元素分为1组，每组20个元素，每个元素之间的增量为1.

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

1. 选择一个增量序列 t1，t2，…，tk，其中 ti > tj，tk = 1；
2. 按增量序列个数 k，对序列进行 k 趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

2、代码实现

public class ShellSort {
    public static void shellSort(int[] arr) {
        // 空数组 或 只有一个元素的数组，则什么都不做。
        if (arr == null || arr.length <= 1) return;
        // 定义希尔增量。
        int gap = arr.length / 2;
        // gap缩小到0的时候就退出循环。
        while (gap != 0) {
            // 每组进行直接插入排序。
            for (int i = gap; i < arr.length; i++) {    // i 代表待插入元素的索引。
                int value = arr[i];
                int j = i - gap;    // j 代表i的上一个元素，相差一个增量gap。
 
                // j < 0 时退出循环，说明 j 是最小的元素的索引值。
                // 或者 arr[j] <= value 时退出循环，说明 j 是比value小的元素的索引值。
                for (; j >= 0 && arr[j] > value; j -= gap) {
                    arr[j + gap] = arr[j];  // 把元素往后挪。
                }
                arr[j + gap] = value;
 
            }
            // 把每一趟排序的结果也输出一下。
            print(arr);
 
            // 缩小增量。
            gap /= 2;
        }
    }
 
    public static void main(String[] args) {
        int[] arr = {6, 9, 1, 4, 5, 8, 7, 0, 2, 3};
 
        System.out.print("排序前:  ");
        print(arr);
 
        shellSort(arr);
 
        System.out.print("排序后:  ");
        print(arr);
    }
 
    // 打印数组
    public static void print(int[] arr) {
        if (arr == null)    return;
 
        for(int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}
/*
排序前:  6 9 1 4 5 8 7 0 2 3 
6 7 0 2 3 8 9 1 4 5 
0 1 3 2 4 5 6 7 9 8 
0 1 2 3 4 5 6 7 8 9 
排序后:  0 1 2 3 4 5 6 7 8 9 
*/

三、冒泡排序

1、原理：比较两个相邻的元素，将值大的元素交换至右端。

2、思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。

3、问题1：代码for(int i = 0;i<array.length - 1;i++)，array.length为什么要减1？答：假设数组只有2个元素，则它们只需要排1趟，假设数组有10个，每一趟会将最大的元素放到最右边，当排了9趟的时候，就有9个元素按大到小在右边排着，此时剩最后一个元素不用排了。因此需要减1。

问题2：代码for (int j = 0;j<array.length-1-i;j++)，为什么要-1-i？答：每经过一趟排序，下一趟的交换次数就会减少1次。

4、代码：

/**
 * @author linwillen
 * @create 2020-04-23-14:04
 */
public class BubbleSort {
 
    public static void main(String[] args) {
        int[] array = {6, 9, 1, 4, 5, 8, 7, 0, 2, 3};
        bubbleSort(array);
        System.out.println(Arrays.toString(arr));
    }
 
    public static void bubbleSort(int[] array){
        for(int i = 0;i<array.length - 1;i++){//外层循环控制排序的趟数
            for (int j = 0;j<array.length-1-i;j++){//内层循环控制每一趟交换的次数
                if(array[j]>array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }
}

四、快速排序

代码：

import java.util.Arrays;
 
/**
 * @author linwillen
 * @create 2020-04-23-14:44
 */
public class QuickSort {
 
    public static int partition(int[] array,int first,int end){
 
        while (first<end){
            while (first < end && array[first] <= array[end]) {
                end--;
            }
            if(first<end){
                int temp = array[first];
                array[first] = array[end];
                array[end] = temp;
                first++;
            }
            while (first < end && array[first] <= array[end]){
                first++;
            }
            if(first<end){
                int temp = array[first];
                array[first] = array[end];
                array[end] = temp;
                end--;
            }
        }
        return first;
    }
 
    public static void quickSort(int[] array,int first,int end){
        if (first < end){
            int pivot = partition(array,first,end);
            quickSort(array,first,pivot - 1);
            quickSort(array,pivot+1,end);
        }
 
    }
 
    public static void main(String[] args) {
        int[] array = {6, 9, 1, 4, 5, 8, 7, 0, 2, 3};
        quickSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }
}

 

五、选择排序

代码实现

import java.util.Arrays;
 
/**
 * @author linwillen
 * @create 2020-04-23-15:51
 */
public class SelectSort {
 
    public static void main(String[] args) {
        int[] array = {6, 9, 1, 4, 5, 8, 7, 0, 2, 3};
        selectSort(array);
        System.out.println(Arrays.toString(array));
    }
 
    public static void selectSort(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[minIndex] > array[j]){
                    minIndex = j;
                }
            }
            if (i != minIndex){
                int temp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = temp;
            }
        }
    }
}

六、堆排序

       堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大根堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小根堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

1、大根堆示意图

性质：该树是完全二叉树，且是从左到右填充。

树的根结点是 A[ 1 ]，若某一结点下标为 i，则很容易得到它的父节点为 i/2，左子结点为 2i，右子结点为 2i + 1。

注意： 数组的索引是 0 开始的，其左右子结点分别为 2i + 1 和 2i + 2。

2、算法：

1. 创建一个堆 H[0……n-1]；

2. 把堆首（最大值）和堆尾互换；

3. 把堆的尺寸缩小1，并调用 Sift()，目的是把新的数组顶端数据调整到相应位置；

4. 重复步骤 2，直到堆的尺寸为 1。

3、代码：

1）调整堆的算法

void Sift(int a[],int k,int m)
{
    int i = k;
    int j = 2*i;
    int temp;
    while(j<=m)
    {
        if(j<m&&a[j]<a[j+1])
            j++;
        if(a[i]>a[j])
            break;
        else
        {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i = j;
            j = 2*i;
        }
    }
}

2）堆排序算法

void HeapSort(int a[],int n)
{
    int i,temp;
    for(i=n/2;i>=1;i--)
        Sift(a,i,n);
    for(i=1;i<n;i++)
    {
        temp = a[1];
        a[1] = a[n-i+1];
        a[n-i+1] = temp;
        Sift(a,i,n-i);
    }
}