排序八大金刚_c语言8大金刚8大简单数学类型

常见的八大排序算法，他们之间关系如下：

代码实现

冒泡排序：

冒泡排序思路比较简单：

1、将序列当中的左右元素，依次比较，保证右边的元素始终大于左边的元素；
（ 第一轮结束后，序列最后一个元素一定是当前序列的最大值；）
2、对序列当中剩下的n-1个元素再次执行步骤1。
3、对于长度为n的序列，一共需要执行n-1轮比较
（利用while循环可以减少执行次数）

实现：

 public static int[] bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length-1; j++) {
                if (arr[i] < arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
1
2
3
4
5
6
7
8
9
10
11
12

快速排序：

1、从序列当中选择一个基准数(pivot)
在这里选择序列当中第一个数最为基准数
2、将序列当中的所有数依次遍历，比基准数大的位于其右侧，比基准数小的位于其左侧
3、重复步骤1.2，直到所有子集当中只有一个元素为止.

public class Quick {
	    /**
	     * 对数组内元素进行排序
	     *
	     * @param a
	     */
	    public static void sort(Comparable[] a) {
	        int lo = 0;
	        int hi = a.length - 1;
	        sort(a, lo, hi);
	    }
	
	    /**
	     * 对数组a中从索引lo到hi之间的元素进行排序
	     *
	     * @param a
	     * @param lo
	     * @param hi
	     */
	    public static void sort(Comparable[] a, int lo, int hi) {
	        //安全校验
	        if (hi <= lo) {
	            return;
	        }
	        //对索引ol到hi的的元素进行分组
	        //获取中间节点
	        int partition = partition(a, lo, hi);
	        //对左边的进行排序
	        sort(a, lo, partition - 1);
	
	        //对右边进行排序
	        sort(a, partition + 1, hi);
	    }
	
	    /**
	     * 对数组a中，从索引lo到hi之将的元素进行分组，并返回分组界限对应的索引
	     *
	     * @param a
	     * @param lo
	     * @param hi
	     * @return
	     */
	    public static int partition(Comparable[] a, int lo, int hi) {
	
	        //分界值
	        Comparable key = a[lo];
	
	        //定义两个值，分别指向切分元素最小和最大的索引的下一个位置
	        int left = lo;
	        int right = hi + 1;
	
	        //切分
	        while (true) {
	            //先从右往左扫描，直到比分界值小的元素
	            while (less(key, a[--right])) {
	                if (right == lo) break;
	            }
	            //从左往右扫描，直到找到比分界值大的元素
	            while (less(a[++left], key)) {
	                if (left == hi) break;
	            }
	            if (left >= right) break;
	            else exch(a, left, right);
	        }
	        exch(a, lo, right);
	        return right;
	    }
	
	    /**
	     * 判断v是否小于w
	     *
	     * @param v
	     * @param w
	     * @return
	     */
	    private static boolean less(Comparable v, Comparable w) {
	        return v.compareTo(w) < 0;
	    }
	
	    /**
	     * 交换a数组中两个索引对应的值
	     *
	     * @param a
	     * @param i
	     * @param j
	     */
	    private static void exch(Comparable[] a, int i, int j) {
	        Comparable t = a[i];
	        a[i] = a[j];
	        a[j] = t;
	    }
	}
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

堆排序：

堆的概念
堆：本质是一种数组对象。特别重要的一点性质：任意的叶子节点小于（或大于）它所有的父节点。对此，又分为大顶堆和小顶堆，大顶堆要求节点的元素都要大于其孩子，小顶堆要求节点元素都小于其左右孩子，两者对左右孩子的大小关系不做任何要求。
利用堆排序，就是基于大顶堆或者小顶堆的一种排序方法。下面，我们通过大顶堆来实现。

基本思想：
堆排序可以按照以下步骤来完成：
1、首先将序列构建称为大顶堆；
（这样满足了大顶堆那条性质：位于根节点的元素一定是当前序列的最大值）
2、构建大顶堆
取出当前大顶堆的根节点，将其与序列末尾元素进行交换；
（此时：序列末尾的元素为已排序的最大值；由于交换了元素，当前位于根节点的堆并不一定满足大顶堆的性质）
对交换后的n-1个序列元素进行调整，使其满足大顶堆的性质；
3、重复2.3步骤，直至堆中只有1个元素为止

/**
     * 堆排序
     *
     * @param arr
     */
    private static void headSort(int[] arr) {
        //把无序的数组转换成有序的堆
        //1、从最后一个非叶子节点开始遍历，
        //2、以这个非叶子节点为父节点，将其转换成大顶堆
        int temp = 0;
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            head(arr, i, arr.length);
        }

        //依次取出堆顶元素，放在数组最后面，直到只有一个元素
        for (int i = arr.length - 1; i > 0; i--) {
           temp =  arr[i];
           arr[i] = arr[0];
           arr[0] = temp;
           head(arr,0,i);
        }
    }
   private static void head(int[] arr, int i, int length) {
//        i * 2 + 1 ---> 以i为父节点的左子叶节点
        int temp = arr[i];
        for (int k = i * 2 + 1; k < length; k = 2 * k + 1) {
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            if (temp < arr[k]) {//与父节点进行比较
                arr[i] = arr[k];
                i = k;//交换位置以后，打破了之前拍的续，所以如果满足条件，就继续遍历
            } else {
                break;
            }
        }
        arr[i] = temp;
    }
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

基数排序：

基数排序：通过序列中各个元素的值，对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。
分配：我们将L[i]中的元素取出，首先确定其个位上的数字，根据该数字分配到与之序号相同的桶中
收集：当序列中所有的元素都分配到对应的桶中，再按照顺序依次将桶中的元素收集形成新的一个待排序列L[ ]
对新形成的序列L[]重复执行分配和收集元素中的十位、百位…直到分配完该序列中的最高位，则排序结束

		/**
		     * 基数排序
		     *
		     * @param arr
		     */
		    public static void radixSort(int[] arr) {
		        //造出十个桶
		        int[][] bucket = new int[10][arr.length];
		        //记录每个桶中存放了多杀数据
		        int[] buckerCounts = new int[10];
		        //获取数组中最大元素，计算出需要循环遍历的次数
		        int max = arr[0];
		        for (int i = 1; i < arr.length; i++) if (arr[i] > max) max = arr[i];
		        //计算出最大的数有多少位
		        String maxString = "" + max;
		        for (int m = 0, n = 1; m < maxString.length(); m++, n *= 10) {
		            //把数据放入桶中
		            for (int i = 0; i < arr.length; i++) {
		                int element = arr[i] / n % 10;
		                bucket[element][buckerCounts[element]++] = arr[i];
		            }
		            int index = 0;//原数组记数
		//            int j = 0;//
		            for (int i = 0; i < buckerCounts.length; i++) {
		                if (buckerCounts[i] != 0) {
		                    for (int j = 0; j < buckerCounts[i]; j++) {
		                        arr[index++] = bucket[i][j];
		                    }
		                }
		                buckerCounts[i] = 0;
		            }
		        }
		    }
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

归并排序：

1、归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个典型的应用。它的基本操作是：将已有的子序列合并，达到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
2、归并排序其实要做两件事：

• 分解----将序列每次折半拆分 合并
• 将划分后的序列段两两排序合并

因此，归并排序实际上就是两个操作，拆分+合并

		/**
		     * 归并排序
		     *
		     * @param arr   //原数组长度
		     * @param left  //每个分组最左边的元素
		     * @param right //最右边的元素
		     * @param temp  //备用数组
		     */
		    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
		        if (left < right) {
		            int mid = (right + left) / 2;
		            //对左边进行分组
		            mergeSort(arr, left, mid, temp);
		            //对右边元素分组
		            mergeSort(arr, mid + 1, right, temp);
		            //分组后合并
		            merge(arr, left, right, mid, temp);
		        }
		    }
		
		    //归并合并
		    public static void merge(int[] arr, int left, int right, int mid, int[] temp) {
		        int i = left;
		        int j = mid + 1;//用两个指针来比较两个分组中的元素大小
		        int index = 0;//表示temp数组中的指针
		        while (i <= mid && j <= right) {
		            if (arr[i] < arr[j]) temp[index++] = arr[i++];
		            else temp[index++] = arr[j++];
		        }
		        //如果比较完后分组中号有多余的元素
		        while (i <= mid) temp[index++] = arr[i++];
		        while (j <= right) temp[index++] = arr[j++];
		        //对数组惊醒拷贝
		        index = 0;
		        for (int k = left; k <= right; k++) arr[k] = temp[index++];
		    }
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

希尔排序：

思想：将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次将gap折半减小，循环上述操作；当 gap=1时，利用直接插入，完成排序。同样的：从上面的描述中我们可以发现：希尔排序的总体实现应该由三个循环完成：

1. 第一层循环：将gap依次折半，对序列进行分组，直到gap=1
2. 第二、三层循环：也即直接插入排序所需要的两次循环。具体描述见上。

		/**
		 * 希尔排序
		 *
		 * @param arr
		 */
		public static void shellSort(int[] arr) {
		    int index = 0;
		    int indexVal = 0;
		    //分组
		    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
		        //对分组遍历
		        for (int i = gap; i < arr.length; i++) {
		            //用插入的思想对每个分组排序
		            index = i;
		            indexVal = arr[i];
		            while (index - gap >= 0 && indexVal < arr[index - gap]) {
		                arr[index] = arr[index - gap];
		                index -= gap;
		            }
		            arr[index] = indexVal;
		        }
		    }
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

选择排序：

简单选择排序的基本思想：比较+交换。

1. 从待排序序列中，找到关键字最小的元素；
2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
3. 从余下的 N - 1个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。 因此我们可以发现，简单选择排序也是通过两层循环实现。第一层循环：依次遍历序列当中的每一个元素 。第二层循环：将遍历得到的当前元素依次与余下的元素进行比较，符合最小元素的条件，则交换。

		/**
		     * 选择排序
		     * 对数组遍历，找出最小的元素，与数组前面的元素交换位置
		     *
		     * @param arr
		     */
		    public static void selectSort(int[] arr) {
		        int index = 0;//记录最小值的索引
		        int temp = 0;
		        for (int i = 0; i < arr.length - 1; i++) {
		            int min = arr[i];
		            index = i;
		            for (int j = i + 1; j < arr.length; j++) {
		                if (arr[j] < min) {
		                    min = arr[j];
		                    index = j;
		                }
		            }
		            temp = arr[i];
		            arr[i] = arr[index];
		            arr[index] = temp;
		        }
		    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

插入排序：

	    /**
	     * 插入排序
	     *
	     * @param arr
	     */
	    public static void insertSort(int[] arr) {
	        int index = 0;//表示有序表的元素的索引
	        int temp = 0;//表示当前从无序表中取出的元素
	        for (int i = 1; i < arr.length; i++) {
	            temp = arr[i];
	            while (index >= 0 && temp < arr[index]) {
	                arr[index + 1] = arr[index];
	                index--;
	            }
	            arr[index + 1] = temp;
	            index = i;
	        }
	    }
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

写完代码后，比较排序的速度：

8w：

插入排序：789ms
选择排序：2925ms
希尔排序：25ms
归并排序：24ms
基数排序：43ms
堆排序：18ms
快速排序：71ms
1
2
3
4
5
6
7

8000w:

快速排序：45671ms
希尔排序：28601ms
归并排序：11797ms（数据量大的时候比堆排序快）
基数排序：OutOfMemoryError: Java heap space(可见基数排序占内存)
堆排序：28390ms
1
2
3
4
5