插入排序和冒泡排序有点像，一个形象的比喻就是打扑克的时候摸牌的时候，也就是手里的牌都是有序的，新插入的找位置，其它元素一次后移
package sort;
import java.util.Arrays;
public class ChaRu {
public static void main(String[] args) {
int arr[] = {2, 25, -5, 36, 89, -6};
chaRu(arr);
System.out.println(Arrays.toString(arr));
}
public static void chaRu(int []arr) {
for(int i=1;i<arr.length;i++){
int j = i-1;
int temp = arr[j + 1];
//while语句里可以不用实现交换 二是单向赋值 给要插的腾位置
while(j>=0){
if(temp<arr[j]){
arr[j + 1] = arr[j];
j--;
}else{
break;
}
}
arr[j + 1] = temp;
}
}
public static void swap(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
插入排序的问题，如果序列是这样 25 88 69 36 255 -1 -2 0 也就是小的数都在后面，这样插入的时候，消耗比较大。希尔排序正是可以解决这个问题的算法，这里给出增量为数组一半的算法
package sort;
import java.util.Arrays;
public class XiEr {
public static void main(String[] args) {
int arr[] = {1, 5, 3, 9, 8, -1, -6, 36, 22, 10};
xiEr(arr);
System.out.println(Arrays.toString(arr));
}
public static void xiEr(int arr[]){
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
for (int j = i-gap; j >= 0; j = j - gap) {
if (arr[j] > arr[j + gap]) {
swap(arr, j, j + gap);
}
}
}
}
}
public static void swap(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
基于选择的排序还有堆排序，属于二叉树的一个应用。而选择排序比较好理解，找到最大（小）的元素，然后交换到第一个
package sort;
import java.util.Arrays;
public class XuanZe {
public static void main(String[] args) {
int arr[] = {5, -5, 8, 45, 6};
xuanZe(arr);
System.out.println(Arrays.toString(arr));
}
public static void xuanZe(int []arr){
int min = -1;
int temp = 0;
for (int i = 0; i < arr.length; i++) {
min = i;
for(int j=i+1;j<arr.length;j++){
if(arr[j]<arr[min])
min = j;
}
swap(arr, min, i);
}
}
public static void swap(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
归并排序的思想是这样的，把数组一分为二，（两个数组都有序），然后把它填入新的数组中。比如 1 5 9 25 和 3 18 20 36 这样新建的数组时间和空间上都是O（N）的代价。
而得到两个有序数组是一个分治的问题，可以用递归解决，出口为数组长度为1 已经有序了。
package sort;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int arr[] = {1, -5, 20, 6, 3};
mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void mergeSort(int arr[],int l ,int r){
if(l>=r)
return;
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
private static void merge(int[] arr, int l, int mid, int r) {
int brr[] = new int[r - l + 1];
int temp = mid+1;
int begin = l;
int i = 0;
while (begin <= mid && temp <= r) {
brr[i++] = arr[begin] > arr[temp] ? arr[temp++] : arr[begin++];
}
while(begin<=mid){
brr[i++] = arr[begin++];
}
while (temp <= r) {
brr[i++] = arr[temp++];
}
System.arraycopy(brr, 0, arr, l, brr.length);
}
}
算法与数据结构 （五） 排序 二 插入排序 希尔排序 选择排序 归并排序
原文：https://www.cnblogs.com/caijiwdq/p/11070715.html