常见排序算法

排序

稳定排序：假设A（3）、B（2）、C（3）、D（4）排序后的结果是BACD。A和C值相同；它们排序前后的顺序是不变的。
概念：稳定排序是 排序前和排序后相等元素的相对位置保持不变的排序算法。一个本身就不稳定的排序 ；不能实现为稳定的排序。

内部排序：数据元素全部放在内存中的排序
外部排序：数据元素太多不能同时放在内存中，需要把待排序或者部分排序的结果存在磁盘。

排序思想

插入法

插入法逐步构建有序序列的排序算法。它从未排序的数据中选择一个元素，将其插入到已排序的序列中的适当位置，直到所有元素都被排序。具体有：直接插入排序、归并排序

选择法

选择法是一种简单直观的排序算法，每次选择未排序部分的最小（或最大）元素，放到已排序部分的末尾。具体有：选择排序

交换法

交换法是通过比较和交换数组中相邻元素的位置来达到排序的目的。具体有：冒泡排序、选择排序

分治法

分治法将一个大问题分解为若干个规模较小且相互独立的子问题，然后递归地解决这些子问题，最后合并子问题的解得到原问题的解。具体有：归并排序、选择排序（一个排序算法的实现可能使用上述的多个方法特性）

常见排序算法

直接插入排序

思想：每次插入多一个数；然后这个数和前面的比较；如果这个数比较小就放到前面去。
i和j相隔1（gap）位置；i从1（gap）位置开始；下来j的5和i的4比较；如果后面比较大就i往下走。如果前面比较大；交换1；j和i都得往前走1（gap）步。（当然实际这个i是不能改变的；但是我们能用j+1表示；结束的条件就是直到j前面没有元素了）

代码实现：

import java.lang.reflect.Array;
import java.util.Arrays;
public class Sort {
    public static void main(String[] args) {
        int []arr={3,5,1,4,2};
        System.out.println(Arrays.toString(insertSort(arr)));
    }
    //插入排序
    public static int[] insertSort(int [] array){
        int i=1;
        for (; i <=array.length-1 ; i++) {
            int tmp=array[i];
            int j=i-1;
        while (j>=0){

            if(array[j]>tmp){
                //进行交换位置
               array[j+1]=array[j];
               array[j]=tmp;
            }
            else {
                break;
            }

            j--;
        }
//            array[j+1]=tmp; 这行代码和前面if里的array[j]=tmp;可以选其1即可。前面的写法是每比较一个就把tmp放进去交换一个次。后面的写法是最后交互完成了才把这个tmp放进去
        }
        return array;
    }
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

时间复杂度（最坏情况下）O（N^2） 公式：1+2+…+(n-1)=n*(n-1)/2 .最好情况O（n）顺序情况
空间复杂度 O（1） 没开辟额外新空间浪费；用完一次循环就回收
稳定性 稳定 {if(array[j] > tmp)就是我们这里不能加等号，如果等了就不稳定;但是稳定的排序也是可以实现为不稳定的形式

希尔排序

比较适用于相对逆序的数排序；插入排序一种。比如：中间间隔5个步数分一组；（处理逆序的极端情况有特殊作用）。每一次gap都是一个插入排序；当gap=1时就是最正宗的直接插入排序。
问题在于：但是这是一个复杂的过程，不知道改分几组，几次结束。尝试gap=gap/2；gap>1的情况

    //希尔排序
    public static void  shellSort(int [] array){
        int gap=array.length;
        while (gap>1){
            gap=gap/2;
//            System.out.println(Arrays.toString(shell(array, gap)));

        }
    }

    public static void shell(int[] array, int gap) {

        for (int i = gap; i <array.length ; i++) {
            int tmp=array[i];
            int j=i-gap;
            while (j>=0){
                if (array[j]>tmp){
                    //交换和更新
                    array[j+gap]=array[j];
                    array[j]=tmp;
                    j=j-gap;
                }else {
                    break;
                }
            }

        }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

时间复杂度：不准确；大概是n的1.3次方
空间复杂度：O(1)
不稳定排序：跳跃式分组；两个相同的数；位置会改变

插入排序和希尔排序思绪是一样的；j和i就是相隔的位置是gap不同的。内循环一定得是用j来表示；因为这是动态变化的；可能会往前比较；j的更新是往前走gap步。

选择排序

每次从待排序的元素中挑选一个最小（或者最大）的放起始位置；直到全部元素有序

找最小值

默认当前位是最小值下标；然后从下一位开始一直与前面这位比较；如果前面的比较小往下走；如果后面的比较小就更新这个最小值下标。遍历出来就交换最小值往到当前位。

    public static void selectsortmin(int []array){
        for (int i = 0; i <array.length-1 ; i++) {
            int minindex=i;
            int min=array[i];
            for (int j = i+1; j <array.length-1 ; j++) {
                if(array[j]<min){
                    minindex=j;
                    min=array[j];
                }
            }
            array[minindex]=array[i];
            array[i]=min;
        }

    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

找最大值

默认最后位是最大值下标；然后从最后一位往前找；如果比这个大则更新下标。否则一直往前。

  public static void selectsortmax(int []array){
        for (int i =array.length-1; i >=0 ; i--) {
            //每一轮下来得重置最大值和其下标
             int  max=array[i];
             int  maxindex=i;
            for (int j =i-1; j >=0 ; j--) {
                if(array[j]>max){
                    max=array[j];
                    maxindex=j;
                }
            }
            array[maxindex]=array[i];
            array[i]=max;
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

选择排序优化

优化思路：定义left往后走；right后往前走；第一次过去就记录下最小和最大值。随后交换位置；直到它们相遇就结束循环
（注意细节：1：最小和最大值在下一次循环得重置；2：如果最大值在开头呢（和left相等）；这种情况特殊针对一下；不然你把最大值换走了我去哪找最大值。

  

    public static void selectsortMax_Min(int []array){
        int left=0;
        int right=array.length-1;
        while (left<right){
            int minindex=left;
            int maxindex=right;
            for (int i = left; i <=right; i++) {
                if(array[i]>array[maxindex]){
                    maxindex=i;
                }
                if(array[i]<array[minindex]){
                    minindex=i;
                }
            }
            //交换涉及4个下标；minindex、maxindex、left、right
            //先交换最小值
            swap(array,minindex,left);
            //交换；注意；如果最大值是第一个得特殊处理；因为你可能被最小值换走了
            if(maxindex==left){
                maxindex=minindex;//之所以等于minIndex；因为最大已经被上面的交换过来了
            }
            //交换最大值
            swap(array,maxindex,right);
            left++;
            right--;
        }
    }
    public static void swap(int[]array,int min_or_maxIndex,int left_or_right){
        int tmp=array[left_or_right];
        array[left_or_right]=array[min_or_maxIndex];
        array[min_or_maxIndex]=tmp;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：不稳定

堆排序

使用标准库的优先级对象：

    public static void heapSort(int []array){
    //堆排序使用优先级队。。。。
        Queue<Integer> queue=new PriorityQueue<>();//默认是小堆还是大堆
        for (int i = 0; i <array.length ; i++) {
            queue.offer(array[i]);
        }
        for (int i = 0; i < array.length; i++) {
            array[i]=queue.poll();
        }

        System.out.println(Arrays.toString(array));

    }
1
2
3
4
5
6
7
8
9
10
11
12
13

如果要排序一组数，从小到大（让下标有序）：
使用小堆：这是不可能实现的；每次弹出最小的没有问题；但是放到哪去；如果放别的地方；空间复杂度就变大了；但是小堆，你也不一定就有序，左右谁大谁小不知道。
使用大堆：每次堆顶和最后一个交换。然后它再自动的排序好大堆。然后我们就不能包含这个最后的元素。交换位置由最后一个元素往前走一步(反之排序建立小堆)我都不用弹出处理交换，直接在原来数组交换。换完排序就好了。所以这才叫堆排序。
代码：

//建堆
  public class TestHeap {
        public int[] elem;
        public int usedSize;//有效的数据个数
        public static final int DEFAULT_SIZE = 10;
        public TestHeap() {
            elem = new int[DEFAULT_SIZE];
        }

        public void initElem(int[] array) {
            for (int i = 0; i < array.length; i++) {
                elem[i] = array[i];
                usedSize++;
            }
        }

        /**
         * 时间复杂度：O(n)
         */
        public void createHeap() {
            for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
                //统一的调整方案
                shiftDown(parent, usedSize);
            }
        }

        private void shiftDown(int parent, int len) {
            int child = 2 * parent + 1;
            //1. 必须保证有左孩子
            while (child < len) {
                //child+1 < len && 保证有右孩子
                if (child + 1 < len && elem[child] < elem[child + 1]) {
                    child++;
                }
                //child下标 一定是左右孩子 最大值的下标
           /* if(elem[child] < elem[child+1] && child+1 < len ) {
                child++;
            }*/
                if (elem[child] > elem[parent]) {
                    int tmp = elem[child];
                    elem[child] = elem[parent];
                    elem[parent] = tmp;
                    parent = child;
                    child = 2 * parent + 1;
                } else {
                    break;
                }
            }
        }

    //堆排序
    public void heapSort(int []array){
        int usedSize=array.length;//usedSize是有效元素个数
        int end=usedSize-1;
        while (end>0){
            //交换0位置和最后的位置；最后的位置放最大值；每次往前走
            int tmp=elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            
            shiftDown(0,end);
            end--;//end传的是数组元素下标，10个元素，我减1。，是不是只调整9个元素。每次结束就少一个元素调整（end--）
        }

    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

时间复杂度：建立堆的复杂度O（n）
O（n） +O（nlogn）约等于O（nlogn）
空间复杂度O（1）；没有浪费，创建额外的空间

冒泡排序

外循环遍历一遍；内循环遍历两两之间；如果前一个元素比后一个元素大就交互位置。这样子每一轮下来就把最大值放到最后面。而后面放好的最大值元素就无需在下一次继续比较。所以循环条件是 j

    //冒泡排序
    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++) {
                //之所以要减i；因为遍历了i次；后面的i个元素已经是最大的排好序
                   if(array[j]>array[j+1]){
                       swap(array,j,j+1);
                   }
            }
        }
        
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度：O（n^2） 优化后最好O（n）
空间复杂度：O（1）
稳定性：稳定