八大快速排序

2019/06/25
  • 八大排序算法

  • 一、直接插入 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度
  • 二、希尔排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度
  • 三、简单选择 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度
  • 四、堆排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度
  • 五、冒泡排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度
  • 六、快速排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度
  • 七、归并排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度
  • 八、基数排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度
  • 总结

八大排序算法

一、直接插入

1.基本思路

在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

2.代码实现

  • 1.遍历数组,每次循环从第二个数字往前插入
  • 2.设定插入数和得到已经排好序列的最后一个数的位数。temp和j=i-1。
  • 3.从最后一个数开始向前循环,如果插入数小于当前数,就将当前数向后移动一位。

public static void insertSort(int[] data) {
    int temp;
    for(int i = 1;i < data.length; i++){// 取第i个数,插入前边的有序的序列
        temp = data[i];
        int j;
        for(j = i - 1; j>=0; j--) {// 从第i-1的位置上开始比较
            if(data[j] > temp) {// 若前面的数大,则往后挪一位
                data[j+1] = data[j];
            } else {
                break;// 否则,说明要插入的数比较大
            }
        }
        data[j+1] = temp;// 找到这个位置,插入数据
    }
}

3.时间复杂度和空间复杂度

直接插入排序的平均复杂度为O(n²),最坏时间复杂度:O(n²),空间复杂度:O(1),没有分配内存。

二、希尔排序

针对直接插入排序下的效率问题,有人对此进行了改进与升级,这就是现在的希尔排序。希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

1.基本思路

  • 1.数的个数为length,i=length/2,将下标差值为i的数分为一组,构成有序序列。
  • 2.再取i=i/2 ,将下标差值为i的数分为一组,构成有序序列。
  • 3.重复第二步,直到k=1执行简单插入排序。

思路:

  • 1.希尔排序(shell sort)这个排序方法又称为缩小增量排序,是1959年D·L·Shell提出来的。该方法的基本思想是:设待排序元素序列有n个元素,首先取一个整数increment(小于n)作为间隔将全部元素分为increment个子序列,所有距离为increment的元素放在同一个子序列中,在每一个子序列中分别实行直接插入排序。然后缩小间隔increment,重复上述子序列划分和排序工作。直到最后取increment=1,将所有元素放在同一个子序列中排序为止。
  • 2.由于开始时,increment的取值较大,每个子序列中的元素较少,排序速度较快,到排序后期increment取值逐渐变小,子序列中元素个数逐渐增多,但由于前面工作的基础,大多数元素已经基本有序,所以排序速度仍然很快。

希尔排序举例: uduipaixuguibingpaixudeng_1.png

2.代码实现

  • 1.遍历数组,每次循环从第二个数字往前插入
  • 2.设定插入数和得到已经排好序列的最后一个数的位数。temp和j=i-1。
  • 3.从最后一个数开始向前循环,如果插入数小于当前数,就将当前数向后移动一位。

(1)首先确定每一组序列的下标的间隔,循环每次需要的间隔:int i = length/2; i >0 ; i /= 2

(2)然后将每一组序列中元素进行插入排序,第二组第一个插入的数字是第一组第一个插入数字之后的那个数组,从i之后每个数字都要进行插入排序,就是插入的序列是各自不同的序列,不是一个一个子序列循环,而是在一个循环中for (int j=i;j<length;j++)完成所有子序列的插入排序。

(3)直到i=0为止。


public static void shellSort(int[] array) {
    int length = array.length;
    for (int i = length / 2; i > 0; i /= 2) {//序列的间隔,一直到间隔为一,这时候就只有一个子序列
        for (int j = i; j < length; j++) {//从i之后每个数字都要进行插入排序,就是插入的序列是各自不同的序列
            int temp = array[j];//里面就是直接插入算法
            int k;
            for (k = j - i; k >= 0; k -= i) {//实现各个数字插入排序到不同的序列中,直到间隔为1的时候,只有一个序列,就是完全的一个直接插入排序
                if (temp < array[k]) {
                    array[k + i] = array[k];
                } else {
                    break;
                }
            }
            array[k + i] = temp;//把数字插入到位置上
        }
    }
    System.out.println(Arrays.toString(array));
}

3.时间复杂度和空间复杂度

希尔排序的平均时间复杂度为O(n²),空间复杂度O(1) 。

三、简单选择

1.基本思路

基本原理如下:对于给定的一组记录,经过第一轮比较后得到最小的记录,然后将该记录的位置与第一个记录的位置交换;接着对不包括第一个记录以外的其他记录进行第二次比较,得到最小记录并与第二个位置记录交换;重复该过程,直到进行比较的记录只剩下一个为止。

2.代码实现

  • 1.确定要插入最小值的位置,从0开始到最后int i = 0; i <len ; i++
  • 2.将每次开始位置上的数字暂定为最小值min,从开始数字之后一个个和min比较,再把最小值存放到min
  • 3.将最小值所在位置上的数字和开始位置上的数字交换

public static void selectSort(int[] array) {
    int len = array.length;
    for (int i = 0; i < len; i++) {//确定每次开始的位置
        int min = array[i];//设定开始数字为最小的值最小值
        int flag = i;
        for (int j = i + 1; j < len; j++) {//把最小值存放到min,从开始数字向后一个个和min比较,再把最小值存放到min
            if (min > array[j]) {
                min = array[j];
                flag = j;
            }
        }
        if (flag != i) {
            array[flag] = array[i];
            array[i] = min;
        }
    }
    System.out.println(Arrays.toString(array));
}

3.时间复杂度和空间复杂度

简单选择排序的时间复杂度为O(n²)

四、堆排序

1.基本思路

  • 1.若array[0,…,n-1]表示一颗完全二叉树的顺序存储模式,则双亲节点指针和孩子结点指针之间的内在关系如下:

任意一节点指针 i
父节点i==0 ? null : (i-1)/2
左孩子2*i + 1
右孩子2*i + 2
  • 2.堆得定义

n个关键字序列array[0...n-1]当且仅当满足下列要求(0 <= i <= (n-1)/2)
 array[i] <= array[2*i + 1]  array[i] <= array[2*i + 2] 称为小根堆
 array[i] >= array[2*i + 1]  array[i] >= array[2*i + 2] 称为大根堆
  • 3.建立大顶堆

n个节点的完全二叉树array[0,…,n-1],最后一个节点n-1是第(n-1-1)/2个节点的孩子。对第(n-1-1)/2个节点为根的子树调整,使该子树称为堆。

对于大根堆,调整方法为:若【根节点的关键字】小于【左右子女中关键字较大者】,则交换。

之后向前依次对各节点((n-2)/2 - 1)~ 0为根的子树进行调整,看该节点值是否大于其左右子节点的值,若不是,将左右子节点中较大值与之交换,交换后可能会破坏下一级堆,于是继续采用上述方法构建下一级的堆,直到以该节点为根的子树构成堆为止。

反复利用上述调整堆的方法建堆,直到根节点。

  • 4.堆排序(大顶堆)

将存放在array[0...n-1]中的n个元素建成初始堆
将堆顶元素与堆底元素进行交换则序列的最大值即已放到正确的位置
将数组中array[0...n-1]前n-1个元素再次形成大根堆再重复第②③直到堆中仅剩下一个元素为止

2.代码实现


/**
    *  大顶堆排序
    * @param array
    */
public static void maxHeapSort(int[] array) {
    int i;
    int len = array.length;
    // 构建大顶堆
    for (i = len / 2 - 1; i >= 0; i--) {
        adjustMaxHeap(array, i, len);
    }
    // 堆顶是最大值,交换堆顶和最后一个数,再重新调整最大堆,下一次循环   i--
    for (i = len - 1; i >= 0; i--) {
        int temp = array[0];
        array[0] = array[i];
        array[i] = temp;
        adjustMaxHeap(array, 0, i);
    }
    System.out.println(Arrays.toString(array));
}
private static void adjustMaxHeap(int[] a, int pos, int len) {
    int temp;
    int child;
    for (temp = a[pos]; 2 * pos + 1 < len; pos = child) {
        // 数组从0开始,r(i)>=r(2i) r(i)>=r(2i+1)  对应 pos => 2 * pos + 1 和 2 * pos +2
        child = 2 * pos + 1;
        // 有右孩子,且右孩子数值更大
        if (child + 1 < len && a[child] < a[child + 1]) {
            child++;
        }
        // 最大的孩子大于根节点
        if (a[child] > temp) {
            a[pos] = a[child];
        } else {
            break;
        }
    }
    a[pos] = temp;
}

3.时间复杂度和空间复杂度

时间复杂度:建堆:o(n),每次调整o(log n),故最好、最坏、平均情况下:o(n*logn);

五、冒泡排序

1.基本思路

一次冒泡将序列中从头到尾所有元素两两比较,将最大的放在最后面。

将剩余序列中所有元素再次两两比较,将最大的放在最后面。

重复第二步,直到只剩下一个数。

2.代码实现


/**
 * @author fupeng
 * 冒泡排序优化第二版
 * 第一版优化增加flag标记,没有数字交换直接return,最优时间复杂度O(n)
 * 第二版优化,增加tempPostion记录内循环最后一次交换的位置,来缩减内循环的次数
 */
public static void bubbleSort(int[] array) {
    int len = array.length - 1;
    // 开辟一个临时空间, 存放交换的中间值
    int temp;
    // 记录最后一次交换的位置
    int tempPostion = 0;
    // 要遍历的次数
    for (int i = 0; i < array.length - 1; i++) {
        int flag = 1; // 设置一个标志位
        // 依次比较相邻两个数的大小,遍历一次后,会将前面没有排好序的最大值放到后面位置
        for (int j = 0; j < len; j++) {
            // 比较相邻的元素,如果前面的数大于后面的数,交换
            if (array[j] > array[j + 1]) {
                temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
                // 发生交换,标志位置0
                flag = 0;
                // 记录交换的位置
                tempPostion = j;
            }
        }
        // 把最后一次交换的位置给len,来缩减内循环的次数
        len = tempPostion;
        // 如果没有交换过元素,则已经有序
        if (flag == 1) {
            System.out.println(Arrays.