常见的基础排序算法大体上可以分为9种,这篇先介绍比较简单的6种排序算法。剩下的3种在下篇介绍。
冒泡排序
冒泡排序通过重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来，直到没有再需要交换的元素为止（对n个项目需要O(n^2)的比较次数）。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
实现步骤
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码
/**
* 冒泡排序
* 最差时间复杂度O(n^2)
* 最优时间复杂度O(n)
* 平均时间复杂度O(n^2)
* 最差空间复杂度O(n) 辅助空间O(1)
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {1, 4, 2, 5, 6, 3};
//bubbleSort(arr);
advancedBubbleSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void bubbleSort(int[] arr) {
int len = arr.length;
int temp;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
/**
* 引入标志位，默认为true
* 如果前后数据进行了交换，则为true，否则为false。如果没有数据交换，则排序完成。
*
* @param arr
*/
public static void advancedBubbleSort(int[] arr) {
boolean flag = true;
int n = arr.length;
while (flag) {
flag = false;
for (int j = 0; j < n - 1; j++) {
if (arr[j] > arr[j + 1]) {
//数据交换
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
//设置标志位
flag = true;
}
}
n--;
}
}
}
插入排序
插入排序将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，是稳定的排序方法。
实现步骤
直接插入排序
把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列。
折半插入排序
折半插入排序,使用使用折半查找的方式寻找插入点的位置, 可以减少比较的次数,但移动的次数不变, 时间复杂度和空间复杂度和直接插入排序一样，在元素较多的情况下能提高查找性能。
代码
private static void insertSort(int[] arr) {
int j;//当前要插入值的位置
int preJ;//依次指向j前的位置
int key;//后移时来暂存要插入的值
//从数组的第二个位置开始遍历值
for (j = 1; j < arr.length; j++) {
key = arr[j];
preJ = j - 1;
//arr[preJ]比当前值大，arr[preJ]后移一位
while (preJ >= 0 && arr[preJ] > key) {
arr[preJ + 1] = arr[preJ]; //将a[preJ]值后移
//这里注意: a[preJ+1]=a[j]=key,把插入值已经存在了 key中
//等于说, 留出来一个空白位置来实现依次后移（不会造成数据丢失问题）
preJ--;//preJ前移
}
//找到要插入的位置或已遍历完成（(preJ=0）
arr[preJ + 1] = key;//将当前值插入 空白位置
}
}
/**
*折半插入排序
*/
private static void binaryInsertSort(int[] arr){
//从数组的第二个位置开始遍历值
for(int i = 1; i < arr.length; i++) {
int key = arr[i];//暂存要插入的值
int pre = 0;//有序序列开始和结尾下标申明
int last = i - 1;
// 折半查找出插入位置 a[pre]
while(pre <= last) {
int mid = (pre + last) / 2;
if(key < arr[mid]) {
last = mid - 1;
} else {
pre = mid + 1;
}
}
//a[i]已经取出来存放在key中，把下标从pre + 1到 i-1的元素依次后移
for(int j = i; j >= pre + 1; j--) {
arr[j] = arr[j - 1];
}
//把值插入空白位置
arr[pre] = key;
}
}
归并排序
归并排序，是创建在归并操作上的一种有效的排序算法该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。 归并排序速度仅次于快速排序，为稳定排序算法（即相等的元素的顺序不会改变），一般用于对总体无序，但是各子项相对有序的数列.
实现步骤
①申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
②设定两个指针，最初位置分别为两个已经排序序列的起始位置
③比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
④重复步骤③直到某一指针到达序列尾
⑤将另一序列剩下的所有元素直接复制到合并序列
代码
private static void mergeSort(int[] arr) {
int len = arr.length;
//用于合并的临时数组
int[] res = new int[len];
int block, start;
//俩俩合并后块大小变大俩倍,(最后一次block等于len)
for (block = 1; block <= len; block *= 2) {
//把整个数组分成很多个块，每次合并处理俩个块
for (start = 0; start < len; start += block * 2) {
int low = start;
int mid = (start + block) < len ? (start + block) : len;
int high = (start + 2 * block) < len ? (start + 2 * block) : len;
//俩个块的起始下标和结束下标
int start1 = start, end1 = mid;
int start2 = mid, end2 = high;
//开始对俩个block进行归并排序
while (start1 < end1 && start2 < end2) {
res[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
}
while (start1 < end1) {
res[low++] = arr[start1++];
}
while (start2 < end2) {
res[low++] = arr[start2++];
}
}
//每次归并后把结果result存入arr中，以便进行下次归并
int[] temp = arr;
arr = res;
res = temp;
}
}
快速排序
基本思想
快速排序（Quicksort）是对冒泡排序的一种改进，又称划分交换排序（partition-exchange sort。
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。实现原理
①．从数列中挑出一个元素，称为"基准"（pivot）
②．重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。 在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
③．递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
代码
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int mid = getMiddle(arr, low, high);
quickSort(arr, low, mid - 1);
quickSort(arr, mid + 1, high);
}
}
private static int getMiddle(int[] arr, int low, int high) {
int temp = arr[low];
while (low < high) {
while (low < high && arr[high] >= temp) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= temp) {
low++;
}
arr[high] = arr[low];
}
arr[low] = temp;
return low;
}
简单选择排序
在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。
最坏情况下，即待排序记录初始状态是按第一条记录最大，之后的记录从小到大顺序排列，则需要移动记录的次数最多为3（n-1）。
简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关
不稳定的排序
代码
public static void simpleSort(int[] arr){
int len = arr.length;
int temp;
for (int i=0;i<len-1;i++){
int min = i;
for (int j=i+1;j<len;j++){//寻找最小的数
if(arr[j]<arr[min]){
min = j;
}
}
if(min!=i){
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}
希尔排序
希尔排序是一个不稳定的排序，其时间复杂度受步长（增量）的影响。
代码
private static void shellSort(int[] arr) {
int gap = 1, i, j, len = arr.length;
int temp;
while (gap < len / 3) {//确定初始步长
gap = gap * 3 + 1;
}
for (; gap > 0; gap /= 3) {//循环遍历步长，最后必为1
for (i = gap; i < len; i++) {//每一列依次向前做插入排序
temp = arr[i];
//每一列中在arr[i]上面且比arr[i]大的元素依次向下移动
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
arr[j + gap] = arr[j];
;
}
//arr[i]填补空白,完成一列中的依次插入排序
arr[j + gap] = temp;
}
}
}
