排序算法
直接插入排序
基本思想
在要排序的一组数中，假设前面(n-1) [n>=2]个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
特点
稳定性： 稳定
平均时间复杂度： O(n^2)
空间复杂度： O(1)
实例
代码
public static void insetSort(int[] arr) {
int len = arr.length;
//默认第一个元素有序，从第二个元素开始比较
for (int j = 1; j < len; j++) {
int temp = arr[j];
int i = j - 1;
//依次比较找到插入位置
while (i >= 0 && arr[i] > temp) {
arr[i + 1] = arr[i];
i--;
}
arr[i+1] = temp;
}
}
Shell排序
基本思想
先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。
特点
稳定性： 不稳定
平均时间复杂度： O(n^1.3)
空间复杂度： O(1)
实例
代码
public static void shellSort(int[] arr) {
int length = arr.length;
int increment = length;
while (true) {
//增量
increment = increment / 2;
//分组处理
for (int i = 0; i < increment; i++) {
//按照直接插入算法处理
for (int j = i+increment; j + increment < length; j += increment) {
int temp = arr[j];
int K = j - increment;
while (K >= 0 && arr[K] > temp) {
arr[K + increment] = arr[K];
K-=increment;
}
arr[K+increment] = temp;
}
}
//增量为1是退出
if (increment == 1) {
break;
}
}
}
简单选择排序
基本思想
基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
特点
稳定性： 不稳定
平均时间复杂度： O(n^2)
空间复杂度： O(1)
实例
代码
public static void selectSort(int[] arr) {
int len = arr.length;
int index = 0;
for (int i = 0; i < len; i++) {
int temp = arr[i];
//查找最大值
for (int j = i + 1; j < len; j++) {
if (temp < arr[j]) {
temp = arr[j];
index = j;
}
}
//交换位置
if (arr[i] != temp) {
SortUtils.swap(arr, i, index);
}
}
}
冒泡排序
基本思想
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
特点
稳定性： 稳定
平均时间复杂度： O(n^2)
空间复杂度： O(1)
实例
代码
public static void bubbleSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len ; i++) {
for (int j = 0; j < len - i - 1; j++) {
if (arr[j] < arr[j + 1]) {
SortUtils.swap(arr, j, j + 1);
}
}
}
}
快速排序
基本思想
选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
特点
稳定性： 不稳定
平均时间复杂度： O(nlgn)
空间复杂度： O(nlgn)
实例
代码
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int middle = getMiddle(arr, low, high); //将list数组进行一分为二
quickSort(arr, low, middle - 1); //对低字表进行递归排序
quickSort(arr, middle + 1, high); //对高字表进行递归排序
}
}
public static int getMiddle(int[] arr, int low, int high) {
int tmp = arr[low]; //数组的第一个作为中轴
while (low < high) {
while (low < high && arr[high] > tmp) {
high--;
}
arr[low] = arr[high]; //比中轴小的记录移到低端
while (low < high && arr[low] < tmp) {
low++;
}
arr[high] = arr[low]; //比中轴大的记录移到高端
}
arr[low] = tmp; //中轴记录到尾
return low; //返回中轴的位置
}
归并排序
基本思想
归并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
特点
稳定性： 稳定
平均时间复杂度： O(nlgn)
空间复杂度： O(n)
实例
代码
//递归划分
public static void mergeSort(int[] data, int left, int right) {
if(left<right){
//找出中间索引
int center=(left+right)/2;
//对左边数组进行递归
mergeSort(data,left,center);
//对右边数组进行递归
mergeSort(data,center+1,right);
//合并
merge(data,left,center,right);
}
}
//合并有序数组
public static void merge(int[] data, int left, int center, int right) {
int [] tmpArr=new int[data.length];
int mid=center+1;
//third记录中间数组的索引
int third=left;
int tmp=left;
while(left<=center&&mid<=right){
//从两个数组中取出最小的放入中间数组
if(data[left]<=data[mid]){
tmpArr[third++]=data[left++];
}else{
tmpArr[third++]=data[mid++];
}
}
//剩余部分依次放入中间数组
while(mid<=right){
tmpArr[third++]=data[mid++];
}
while(left<=center){
tmpArr[third++]=data[left++];
}
//将中间数组中的内容复制回原数组
while(tmp<=right){
data[tmp]=tmpArr[tmp++];
}
System.out.println(Arrays.toString(data));
}
