排序算法 冒泡排序 选择排序 插入排序 希尔排序 快速排序 归并排序 基数排序（桶排序）
排序算法
排序，给定一组数，按照指定顺序进行排列的过程。
排序算法有很多，一般可以分为二类：
内部排序，即使用内存
- 插入排序：直接插入排序、希尔排序
- 选择排序：简单选择排序、堆排序
- 交换排序：冒泡排序、快速排序
- 归并排序
- 基数排序
- 外部排序，使用内存+外部存储
各个算法时间复杂度比较：
术语说明：
- 稳定：如果
a原来就在b前面，而a = b，完成排序后a仍在b的前面。 - 不稳定：如果
a原来就在b前面，而a = b，完成排序后a可能在b的后面。 - 内排序（In-place）：所有操作都在内存中完成。
- 外排序（Out-place）：由于数据太大，因而将数据放在磁盘中，排序操作通过外部存储和内存的数据传输才能进行。
- 时间复杂度：算法执行所耗费的时间。
- 空间复杂度：算法运行所需内存大小。
冒泡排序
冒泡排序思想：
通过对待排序序列从前向后，依次比较相邻的元素，逆序则交换，使得值较大的元素逐渐从前移到后部，类似冒泡从底部逐渐冒上来（排好序）。
冒泡排序代码如下：
/**
* 冒泡排序
* <pre>
* 重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序逆序(即排序标准)就把他们交换过来。
* 走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
* </pre>
* @author jyoryo
*/
public class BubbleSort {
public static void main(String[] args) {
int size = 100000;
int array[] = new int[size];
for(int i = 0; i < size; i++) {
array[i] = (int)(Math.random() * size * 1000);
}
// System.out.println(Arrays.toString(array));
long current = System.nanoTime();
// bubbleSort(array);
bubbleSort2(array);
System.out.println(System.nanoTime() - current);
// System.out.println(Arrays.toString(array));
}
// 冒泡排序
public static void bubbleSort(int[] array) {
int length = array.length;
for(int i = 0; i < length; i ++) {
for(int j = 0; j < (length - i - 1); j ++) {
if(array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
}
// 冒泡排序（优化过）
public static void bubbleSort2(int [] array) {
int length = array.length;
boolean flag = false; //标志是否经过交换
for(int i = 0; i < length; i++) {
for(int j = 0; j < (length - i - 1); j++) {
if(array[j] > array[j + 1]) {
flag = true;
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
// 在一趟排序中未发生交换
if(!flag) {
break ;
}
// 重置标志
flag = false;
}
}
}选择排序
简单选择排序是一种简单直观的算法。
基本思想：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序代码如下：
/**
* 选择排序
* <pre>
* 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
* 然后，再从剩余未排序元素中继续寻找最小（大）元素，
* 然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
* </pre>
* @author jyoryo
*/
public class SelectSort {
public static void main(String[] args) {
int size = 100000;
int array[] = new int[size];
for(int i = 0; i < size; i++) {
array[i] = (int)(Math.random() * size * 1000);
}
// System.out.println(Arrays.toString(array));
long current = System.nanoTime();
selectSort(array);
System.out.println(System.nanoTime() - current);
// System.out.println(Arrays.toString(array));
}
public static void selectSort(int[] array) {
int length = array.length;
for(int i = 0; i < length - 1; i ++) {
int minIndex = i;
for(int j = (i + 1); j < length; j++) {
if(array[minIndex] > array[j]) {
minIndex = j;
}
}
if(i != minIndex) {
int tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}
}
}
}插入排序
插入排序是属于内部排序，其排序思想是：
将n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含n-1个元素。排序过程中每次从无序表中取出第一个元素，将它与有序表元素进行比较，然后将它插入到有序表中的适当位置，使之成为新的有序表。
插入排序算法代码如下：
/**
* 插入排序
* @author jyoryo
*/
public class InsertSort {
public static void main(String[] args) {
int size = 100000;
int array[] = new int[size];
for(int i = 0; i < size; i++) {
array[i] = (int)(Math.random() * size * 1000);
}
// System.out.println(Arrays.toString(array));
long current = System.nanoTime();
insertSort(array);
System.out.println(System.nanoTime() - current);
// System.out.println(Arrays.toString(array));
}
public static void insertSort(int[] array) {
int length = array.length;
for(int i = 1; i < length; i++) {
int currentValue = array[i];
int insertIndex = i - 1;
while(insertIndex >= 0 && array[insertIndex] > currentValue) {
array[insertIndex + 1] = array[insertIndex];
insertIndex --;
}
if(i != (insertIndex + 1)) {
array[insertIndex + 1] = currentValue;
}
}
}
}希尔排序
希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
算法思想：
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序代码如下：
/**
* 希尔排序(缩小增量排序)
* @author jyoryo
*/
public class ShellSort {
public static void main(String[] args) {
int size = 100000;
int[] array = new int[size];
for(int i = 0; i < size; i++) {
array[i] = (int)(Math.random() * size * 1000);
}
// System.out.println(Arrays.toString(array));
long current = System.nanoTime();
shellSort(array);
System.out.println(System.nanoTime() - current);
// System.out.println(Arrays.toString(array));
}
public static void shellSort(int[] array) {
int length = array.length;
int tmp = 0;
for(int gap = (length / 2); gap > 0; gap /= 2) {
for(int i = gap; i < length; i++) {
int j = i;
tmp = array[i];
if(array[j] < array[j - gap]) {
// 移位法
while((j - gap) >= 0 && tmp < array[j - gap]) {
array[j] = array[j - gap];
j -= gap;
}
array[j] = tmp;
}
}
}
}
}快速排序
快速排序是对冒泡排序的一种改进。
基本思想：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分所有数据都比另一部分的所有数据都要小，然后按照此方法对两部分数据分别进行快速排序（使用递归）。
快速排序代码如下：
/**
* 快排算法
* <pre>
* 快速排序由于排序效率在同为 O(nlogn) 的几种排序方法中效率最高.
* 该方法的基本思想是：
* 1．先从数列中取出一个数作为基准数；
* 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边；
* 3．再对左右区间重复第二步，直到各区间只有一个数。
* </pre>
* @author jyoryo
*
*/
public class QuickSort {
public static void main(String[] args) {
int size = 100000;
int[] array = new int[size];
for(int i = 0; i < size; i++) {
array[i] = (int)(Math.random() * size * 1000);
}
// System.out.println(Arrays.toString(array));
long current = System.nanoTime();
quickSort(array, 0, array.length - 1);
System.out.println(System.nanoTime() - current);
// System.out.println(Arrays.toString(array));
}
/**
* 排序
* @param array
* @param low
* @param hight
*/
public static void quickSort(int array[], int low, int hight) {
if(low > hight) {
return ;
}
// 左标记:i 右标记:j 基准值：tmp(默认第一个)
int i, j, tmp;
i = low;
j = hight;
tmp = array[i];
// 排序：将找到比基准数大的在基准值右侧；将找到比基准值小的在基准值左侧
while(i < j) {
// 从右向左扫描(找到第一个比基准数小的数)
while(i < j && array[j] >= tmp) {
j--;
}
if(i < j) {
// 可以简写为：a[i++] = a[j];
array[i] = array[j];
i ++;
}
// 从左向右扫描(找到第一个比基准数大的数)
while(i < j && array[i] < tmp) {
i ++;
}
if(i < j) {
// 可以简写为：a[j--] = a[i];
array[j] = array[i];
j --;
}
}
// i为中间值
array[i] = tmp;
// 左侧数据递归快速排序
quickSort(array, low, i - 1);
// 右侧数据递归快速排序
quickSort(array, i + 1, hight);
}
}归并排序
归并排序是利用归并的思想实现的排序算法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分divide成一些小的问题然后递归求解，而治conquer的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
归并排序代码如下：
/**
* 归并排序
* @author jyoryo
*/
public class MergeSort {
public static void main(String[] args) {
int size = 100000;
int array[] = new int[size];
for(int i = 0; i < size; i++) {
array[i] = (int)(Math.random() * size * 1000);
}
// System.out.println(Arrays.toString(a));
long current = System.nanoTime();
mergeSort(array, 0, size - 1, new int[size]);
System.out.println(System.nanoTime() - current);
// System.out.println(Arrays.toString(a));
}
public static void mergeSort(int[] array, int left, int right, int[] temp) {
if(left >= right) {
return ;
}
int middle = (int)((left + right) / 2);
// 左边的数组拆分
mergeSort(array, left, middle, temp);
// 右边的数组拆分
mergeSort(array, middle + 1, right, temp);
// 合并
merge(array, left, middle, right, temp);
}
// 合并
public static void merge(int[] array, int left, int middle, int right, int[] temp) {
int i = left; // 左边数组的当前索引
int j = middle + 1; //右边数组的当前索引
int t = 0; //临时数组当前的索引
// 1、比较左右两边数组元素，将小的拷贝至临时数组
while(i <= middle && j <= right) {
if(array[i] <= array[j]) {
// 可以简写为： temp[t++] = array[i++];
temp[t] = array[i];
i++; t++;
} else {
// 可以简写为： temp[t++] = array[j++];
temp[t] = array[j];
j++; t++;
}
}
// 2、将左/右数组剩下的元素拷贝至临时数组
while(i <= middle) {
// 可以简写为： temp[t++] = array[i++];
temp[t] = array[i];
i++; t++;
}
while(j <= right) {
// 可以简写为： temp[t++] = array[j++];
temp[t] = array[j];
j++; t++;
}
// 3、将临时数组拷贝至原数组
t = 0;
while(left <= right) {
// 可以简写为： temp[t++] = array[left++];
array[left] = temp[t];
left++; t++;
}
}
}基数排序
基数排序又称桶排序。
该排序算法思想：
将所有待比较数值（须是正整数）统一为同样的数位长度,数位较短的数前面补零； 然后, 从最低位开始, 依次进行一次稳定排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序说明：
- 速度快，是对传统桶排序的扩展
- 是经典空间换时间的方式，占用内存很大，对海量数据进行排序时，容易造成
OutOfMemoryError。 - 稳定排序。
基数排序算法代码如下：
/**
* 基数排序（桶排序）
* @author jyoryo
*/
public class RadixSort {
public static void main(String[] args) {
int size = 100000;
int [] array = new int[size];
for(int i = 0; i < size; i++) {
array[i] = (int)(Math.random() * size * 1000);
}
// System.out.println(Arrays.toString(array));
long current = System.nanoTime();
radixSort(array);
System.out.println(System.nanoTime() - current);
// System.out.println(Arrays.toString(array));
}
public static void radixSort(int [] array) {
int length = array.length;
// 找到最大数
int max = array[0];
for(int i = 1; i < length; i++) {
if(array[i] > max) {
max = array[i];
}
}
// 根据最大数确定位数
int maxLength = String.valueOf(max).length();
// 桶
int [][] bucket = new int[10][length];
int [] bucketCounter = new int[10]; // 每个桶元素个数计数器
for(int i = 0, n = 1; i < maxLength; i++, n *= 10) {
// 遍历所有数，根据对位位数的数字放置在对应数字的桶中
for(int j = 0; j < length; j++) {
int digitOfNo = array[j] / n % 10;
bucket[digitOfNo][bucketCounter[digitOfNo]] = array[j];
bucketCounter[digitOfNo] ++;
}
// 从桶中取出数放回数组
int index = 0;
for(int k = 0; k < bucketCounter.length; k++) {
if(bucketCounter[k] > 0) {
for(int l = 0; l < bucketCounter[k]; l++) {
array[index++] = bucket[k][l];
}
}
// 重要：桶元素计数器重置
bucketCounter[k] = 0;
}
}
}
}