几种常见的排序方法

1.冒泡排序

基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。

每次循环将最大的元素放到数组最后

子循环第一次排序，将最大的数放到最后，第二次循环，将第二大的数放到倒数第二的位置...以此类推。（适合小数据量排序）

对数组int[] a = {12,2,45,23,9,88,33,23,22,5,4,4,5,1,9,7,2,7,8};按从小到大的顺序排列。

代码：

/**

* 冒泡排序。从小到大排序。<br>

* 基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。<br>

* 子循环第一次排序，将最大的数放到最后，第二次循环，将第二大的数放到倒数第二的位置...以此类推。<br>

* @param source

* @return

*/

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

 

for (int i = 1; i < source.length; i++) {

for (int j = 0; j < source.length - i; j++) {

if (source[j] > source[j+1]) {

int temp = source[j];

source[j] = source[j+1];

source[j+1] = temp;

}

}

// 输出每个子循环排序后的数组中的元素

printArray(source,i);

}

return source;

}

 

/**

* 循环输出数组中的元素。

* @param a

* @param idx，第一层循环的index

*/

public static void printArray(int[] a,int idx) {

for (int i = 0; i < a.length; i++) {

System.out.print(a[i]);

if (i != a.length - 1) {

System.out.print(",");

}

}

System.out.println("---" + idx);

}

 

看看输出的结果：

2,12,23,9,45,33,23,22,5,4,4,5,1,9,7,2,7,8,88---1

2,12,9,23,33,23,22,5,4,4,5,1,9,7,2,7,8,45,88---2

2,9,12,23,23,22,5,4,4,5,1,9,7,2,7,8,33,45,88---3

2,9,12,23,22,5,4,4,5,1,9,7,2,7,8,23,33,45,88---4

2,9,12,22,5,4,4,5,1,9,7,2,7,8,23,23,33,45,88---5

2,9,12,5,4,4,5,1,9,7,2,7,8,22,23,23,33,45,88---6

2,9,5,4,4,5,1,9,7,2,7,8,12,22,23,23,33,45,88---7

2,5,4,4,5,1,9,7,2,7,8,9,12,22,23,23,33,45,88---8

2,4,4,5,1,5,7,2,7,8,9,9,12,22,23,23,33,45,88---9

2,4,4,1,5,5,2,7,7,8,9,9,12,22,23,23,33,45,88---10

2,4,1,4,5,2,5,7,7,8,9,9,12,22,23,23,33,45,88---11

2,1,4,4,2,5,5,7,7,8,9,9,12,22,23,23,33,45,88---12

1,2,4,2,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88---13

1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88---14

1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88---15

1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88---16

1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88---17

1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88---18

从第1行到第14行，

第1行，取出原数组的最大数放到最后，即88被放到了数组最后位置。（内层循环中比较的元素是0-source.length-1，即第1次比较的是全部数组元素）。

第2行，从第一次排序后的结果中取出最大数放到最后（内层循环中比较的元素是0-source.length-2，即上面第1行标颜色的部分）

第3行，从第二次排序后的结果中取出最大的数放到最后（上面第二行标颜色的部分）。

…

依此类推，但是到了14行，即上面标黄的部分，那里就已经排序完毕了（也就是已经从小到大排序完了），那么后面几次的循环是没必要的。

那么如果解决这个问题呢？

改进的代码如下：

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

boolean isSort = false; // 是否排序

 

for (int i = 1; i < source.length; i++) {

isSort = false; // 在每次排序前都初始化为false

for (int j = 0; j < source.length - i; j++) {

if (source[j] > source[j+1]) {

int temp = source[j];

source[j] = source[j+1];

source[j+1] = temp;

 

isSort = true; // 为TRUE表明此次循环（外层循环）有排序。

}

}

 

if (!isSort) break; // 如果没有排序，说明数据已经排序完毕。

// 输出每个子循环排序后的数组中的元素

printArray(source,i);

}

return source;

}

 

2.选择排序

原理：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。（适合小数据量排序）

代码：

/**

* 原理：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

* 选择排序。从小到大排序

* @param source

* @return

*/

public static int[] selectSort(int[] source) {

int min_idx = -1; // 当此循环所有元素最小元素所在的下标。

 

for (int i = 0; i < source.length-1; i++) {

min_idx = i; // 以i为界，将数组分为前后2部分。

for (int j = i+1; j < source.length; j++) { // i之后的数组元素

if (source[j] < source[min_idx]) { // 后面部分的数组中有元素小于前部分，循环取出最小的一个值的下标

min_idx = j;

}

}

if (min_idx != i) { // 如果min_idx = i说明后面部分的数组没有元素值大于前面部分。否则将后面部分最小的元素移到前面。

int temp = source[i];

source[i] = source[min_idx];

source[min_idx] = temp;

}

printArray(source, i);

}

 

return source;

}

 

测试数据：int[] a = {12,2,45,23,9,88,33,23,22,5,4,4,5,1,9,7,2,7,8,0};

程序输出：

0,2,45,23,9,88,33,23,22,5,4,4,5,1,9,7,2,7,8,12---0

0,1,45,23,9,88,33,23,22,5,4,4,5,2,9,7,2,7,8,12---1

0,1,2,23,9,88,33,23,22,5,4,4,5,45,9,7,2,7,8,12---2

0,1,2,2,9,88,33,23,22,5,4,4,5,45,9,7,23,7,8,12---3

0,1,2,2,4,88,33,23,22,5,9,4,5,45,9,7,23,7,8,12---4

0,1,2,2,4,4,33,23,22,5,9,88,5,45,9,7,23,7,8,12---5

0,1,2,2,4,4,5,23,22,33,9,88,5,45,9,7,23,7,8,12---6

0,1,2,2,4,4,5,5,22,33,9,88,23,45,9,7,23,7,8,12---7

0,1,2,2,4,4,5,5,7,33,9,88,23,45,9,22,23,7,8,12---8

0,1,2,2,4,4,5,5,7,7,9,88,23,45,9,22,23,33,8,12---9

0,1,2,2,4,4,5,5,7,7,8,88,23,45,9,22,23,33,9,12---10

0,1,2,2,4,4,5,5,7,7,8,9,23,45,88,22,23,33,9,12---11

0,1,2,2,4,4,5,5,7,7,8,9,9,45,88,22,23,33,23,12---12

0,1,2,2,4,4,5,5,7,7,8,9,9,12,88,22,23,33,23,45---13

0,1,2,2,4,4,5,5,7,7,8,9,9,12,22,88,23,33,23,45---14

0,1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,88,33,23,45---15

0,1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,88,45---16

0,1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,88,45---17

0,1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88---18

这是从小到大排序的结果，

第1次循环，取出数组中最小的元素放在数组第一个位置；

第2次循环，取出剩余待排序数组中最小的值1，放到待排序数组的第1位；

…

第1次循环，已经排好的元素：无；比较的元素，左边：12，右边：剩余元素。

第2次循环，已经排好的元素：0，不参与后面的排序；比较的元素，左边：2，右边：数组中除已经已经排好的元素和左边的元素之外的元素。

…

最后一次，已经排好的元素：0,1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33，不参与后面的排序；比较的元素，左边：88；右边：45。

上面标注颜色的部分是不参与下一次排序（或比较）的元素。

 

3.插入排序

每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。（适合小数据量排序）

 

代码：

/**

* 插入排序，从小到大。

* @param source

* @return

*/

public static int[] insertSort(int[] source) {

for (int i = 1; i < source.length; i++) {

int idx = i;

int data = source[idx];

 

while ((idx > 0 && source[idx-1] > data)) {

source[idx] = source[idx-1];

idx--;

}

 

source[idx] = data;

printArray(source, i);

}

return source;

}

测试数据：int[] a = {12,2,45,23,9,88,33,23,22,5,4,4,5,1,9,7,2,7,8,0};

输出：

2,12,45,23,9,88,33,23,22,5,4,4,5,1,9,7,2,7,8,0---1—》12与2比较

2,12,45,23,9,88,33,23,22,5,4,4,5,1,9,7,2,7,8,0---2—》45与2，12比较

2,12,23,45,9,88,33,23,22,5,4,4,5,1,9,7,2,7,8,0---3—》23与2，12，45比较

2,9,12,23,45,88,33,23,22,5,4,4,5,1,9,7,2,7,8,0---4—》9与2，12，13，45比较

2,9,12,23,45,88,33,23,22,5,4,4,5,1,9,7,2,7,8,0---5—》88与2，9，12，23，45比较

2,9,12,23,33,45,88,23,22,5,4,4,5,1,9,7,2,7,8,0---6

2,9,12,23,23,33,45,88,22,5,4,4,5,1,9,7,2,7,8,0---7

2,9,12,22,23,23,33,45,88,5,4,4,5,1,9,7,2,7,8,0---8

2,5,9,12,22,23,23,33,45,88,4,4,5,1,9,7,2,7,8,0---9

2,4,5,9,12,22,23,23,33,45,88,4,5,1,9,7,2,7,8,0---10

2,4,4,5,9,12,22,23,23,33,45,88,5,1,9,7,2,7,8,0---11

2,4,4,5,5,9,12,22,23,23,33,45,88,1,9,7,2,7,8,0---12

1,2,4,4,5,5,9,12,22,23,23,33,45,88,9,7,2,7,8,0---13

1,2,4,4,5,5,9,9,12,22,23,23,33,45,88,7,2,7,8,0---14

1,2,4,4,5,5,7,9,9,12,22,23,23,33,45,88,2,7,8,0---15

1,2,2,4,4,5,5,7,9,9,12,22,23,23,33,45,88,7,8,0---16

1,2,2,4,4,5,5,7,7,9,9,12,22,23,23,33,45,88,8,0---17

1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88,0---18

0,1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88---19

标黄的是排好序的，后面的是未排序的。用未排序的第1个元素与前面排好序的元素比较，确定未排序的第一个元素的插入位置。

4.快速排序

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。（适合大量数据排序）

/**

* 快速排序。<br>

* 思想：选定一个元素作为枢纽元素，将小于该元素的元素放到左边，大于该元素的放到右边。不断重复此过程。<br>

* 直到最终形成一个有序的列表。<br>

* 下面的参数low,high就是可以支持一个数组的一个子区间进行排序。<br>

* 如果是整个数组进行排序，则low=0,high=数组.length-1。

* @param data:要排序的数组。

* @param low:排序的起始位置

* @param high:排序的结束位置。

*/

public static void quicksort(int[] data,int low,int high) {

int i=low,j=high;

 

if (low < high) {

// 枢纽元素

int key = data[i];

System.out.println("枢纽元素是：" + key + ",low:" + low + ",high:" + high);

 

while (i < j) {

// 从右往左判断，将小于枢纽元素的元素放到枢纽元素左边。

while (i < j && data[j] > key) {

j--;

}

 

if (i < j) {

data[i] = data[j];

i++;

}

 

// 从左往右判断，将大于枢纽元素的元素放到枢纽元素右边

while (i < j && data[i] < key) {

i++;

}

 

if (i < j) {

data[j] = data[i];

j--;

}

 

data[i] = key;

}

 

printArray(data);

 

// 递归将枢纽元素左边的元素再分成2部分，将小于新枢纽元素的元素放到左边；大于新枢纽元素的元素放到右边。

quicksort(data,low,i-1);

// 递归右边

quicksort(data,i+1,high);

}

}

测试：

int[] a = { 12, 2, 45, 23, 9, 88, 33, 23, 22, 5, 4, 4, 5, 1, 9, 7, 2,

7, 8, 0 };

// 从第6个元素开始，看到第16个元素，即只对这一个范围内的元素进行排序（标黄的部分）。

quicksort(a, 5, 15);

排序过程：

枢纽元素是：88,low:5,high:15

12,2,45,23,9,7,33,23,22,5,4,4,5,1,9,88,2,7,8,0

枢纽元素是：7,low:5,high:14

12,2,45,23,9,1,5,4,4,5,7,22,23,33,9,88,2,7,8,0

枢纽元素是：1,low:5,high:9

12,2,45,23,9,1,5,4,4,5,7,22,23,33,9,88,2,7,8,0

枢纽元素是：5,low:6,high:9

12,2,45,23,9,1,5,4,4,5,7,22,23,33,9,88,2,7,8,0

枢纽元素是：5,low:6,high:8

12,2,45,23,9,1,4,4,5,5,7,22,23,33,9,88,2,7,8,0

枢纽元素是：4,low:6,high:7

12,2,45,23,9,1,4,4,5,5,7,22,23,33,9,88,2,7,8,0

枢纽元素是：22,low:11,high:14

12,2,45,23,9,1,4,4,5,5,7,9,22,33,23,88,2,7,8,0

枢纽元素是：33,low:13,high:14

12,2,45,23,9,1,4,4,5,5,7,9,22,23,33,88,2,7,8,0

标黄的部分即是排序的部分。