简书链接:常见排序算法巩固附上经典视频教程
文章字数：657,阅读全文大约需要2分钟
冒泡排序

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

public static int[] bubbleSort(int[] array) {

       for (int i = 0; i < array.length; i++) {
           for (int j = 0; j < array.length-i-1; j++) {
               if (array[j] > array[j+1]) {
                   int temp = array[j];
                   array[j] = array[j+1];
                   array[j+1] = temp;
               }
            
          
           }
       }
    
       return array;
   }

image.png

上面的代码是把每一个进行遍历然后写一个内循环进行啰嗦重复的遍历
选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int[] selectSort(int[] array) {
	
		for (int i = 0; i < array.length - 1; i++) {//最后一个不需要比较了,
			for (int j = i+1; j < array.length; j++) {
				if (array[i] > array[j]) {
					int temp = array[i];
					array[i] = array[j];
					array[j] = temp;
				}
				
				
			}
		}
		
		return array;
	}

选择排序的特点是一次从头开始往后面比较,每次循环 头部开始位置就会+1,
冒泡排序不同,冒泡排序是相邻的2个进行比较, 如0和1 的索引值比较完毕之后 1 和 2 比较 ,
插入排序

1
2
3
4
5
6
7
8
9
10
11
12
public static int[] sort(int[] array) {
       for (int i = 1; i < array.length; i++) {
           int temp = array[i];
           int in = i;
           while (in > 0 && array[in-1] >= temp) {
               array[in] = array[in-1];
               in--;
           }
           array[in] = temp;
       }
       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
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

/**
 * Sorts the specified range of the array using the given
 * workspace array slice if possible for merging
 *
 * @param a the array to be sorted
 * @param left the index of the first element, inclusive, to be sorted
 * @param right the index of the last element, inclusive, to be sorted
 * @param work a workspace array (slice)
 * @param workBase origin of usable space in work array
 * @param workLen usable size of work array
 */
static void sort(long[] a, int left, int right,
                 long[] work, int workBase, int workLen) {
    // Use Quicksort on small arrays
    if (right - left < QUICKSORT_THRESHOLD) {
        sort(a, left, right, true);
        return;
    }

    /*
     * Index run[i] is the start of i-th run
     * (ascending or descending sequence).
     */
    int[] run = new int[MAX_RUN_COUNT + 1];
    int count = 0; run[0] = left;

    // Check if the array is nearly sorted
    for (int k = left; k < right; run[count] = k) {
        if (a[k] < a[k + 1]) { // ascending
            while (++k <= right && a[k - 1] <= a[k]);
        } else if (a[k] > a[k + 1]) { // descending
            while (++k <= right && a[k - 1] >= a[k]);
            for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
                long t = a[lo]; a[lo] = a[hi]; a[hi] = t;
            }
        } else { // equal
            for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
                if (--m == 0) {
                    sort(a, left, right, true);
                    return;
                }
            }
        }

        /*
         * The array is not highly structured,
         * use Quicksort instead of merge sort.
         */
        if (++count == MAX_RUN_COUNT) {
            sort(a, left, right, true);
            return;
        }
    }

    // Check special cases
    // Implementation note: variable "right" is increased by 1.
    if (run[count] == right++) { // The last run contains one element
        run[++count] = right;
    } else if (count == 1) { // The array is already sorted
        return;
    }

    // Determine alternation base for merge
    byte odd = 0;
    for (int n = 1; (n <<= 1) < count; odd ^= 1);

    // Use or create temporary array b for merging
    long[] b;                 // temp array; alternates with a
    int ao, bo;              // array offsets from 'left'
    int blen = right - left; // space needed for b
    if (work == null || workLen < blen || workBase + blen > work.length) {
        work = new long[blen];
        workBase = 0;
    }
    if (odd == 0) {
        System.arraycopy(a, left, work, workBase, blen);
        b = a;
        bo = 0;
        a = work;
        ao = workBase - left;
    } else {
        b = work;
        ao = 0;
        bo = workBase - left;
    }

    // Merging
    for (int last; count > 1; count = last) {
        for (int k = (last = 0) + 2; k <= count; k += 2) {
            int hi = run[k], mi = run[k - 1];
            for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
                if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
                    b[i + bo] = a[p++ + ao];
                } else {
                    b[i + bo] = a[q++ + ao];
                }
            }
            run[++last] = hi;
        }
        if ((count & 1) != 0) {
            for (int i = right, lo = run[count - 1]; --i >= lo;
                b[i + bo] = a[i + ao]
            );
            run[++last] = right;
        }
        long[] t = a; a = b; b = t;
        int o = ao; ao = bo; bo = o;
    }
}

image.png

不过原理就是把数据分成两部分进行排序,有一个图非常清晰的,

从上面插入排序代码看上去好像差不多的样子,但是while循环的条件是和当前index-1以及-….都要比外循环index的值才进行不断的内while循环递减替换比较,不满足就不会进行了,所以优点就是处理有序数量较多的时候有优势.
image.png
https://www.cnblogs.com/www-1761735951-com/p/5985952.html
http://www.iqiyi.com/w_19rs84lwkl.html
http://www.cnblogs.com/ershao/category/823714.html
http://v.youku.com/v_show/id_XNDgwMjY5MDQw.html
http://yun.itheima.com/course/7.html
快速排序参考
https://www.cnblogs.com/MOBIN/p/4681369.html
http://blog.jobbole.com/11745/
选择排序和冒泡排序循环次数是一样的,区别在哪里 冒泡排序是相邻的比较,而选择排序是从0开始依次往后面开始比较然后index+1再依次往后面查找.