01 插入排序–直接插入排序

思路：将待排序的无序数组中的每第一个元素arr[j]，插入到前面的有序数组中arr[0]...ar[j-1]
为arr[j]在有序数组中找到对应的插入位置p,那么需要将p...j-1这几个元素都向后移动，为了防止arr[j]的值被覆盖，因此先将arr[j]的值存储起来。
//默认整个数组的第一个元素就是有序数组的第一个元素，因此无序数组从数组的第二个开始
for(int i =1; i<arr.length; i++){
//令j指向当前i的位置，原因是：因为在后移动的时候将j--，如果设置为j=i-1，虽然逻辑上理解起来是这样没错，但是数组的j很可能减少到-1int j = i;int temp = arr[i];while(j>0 && arr[j-1] > arr[i]){//使元素往后移动arr[j] = arr[j-1];j--;}arr[j] = temp;
}

02 插入排序–希尔排序

public void XierInsertSort(int arr[], int dk){for(int i = dk; i<arr.length; i++){if(arr[i] < arr[i-dk]){int cur = arr[i];for(int j=i-dk; j>=0&& cur<arr[i-dk]; j=j-dk){arr[j+dk] = arr[j];}arr[j] = cur;}}
}
public void XierSort(int arr[]){dk = arr.length/2;while(dk>=1){XierInsertSort(int arr[], dk);dk /= 2;}
}

03 选择排序—简单选择排序

打擂台法：
//控制擂主需要循环几次
for(int i=0; i<arr.length-1; i++){int LeiZhu = i;//控制擂主与剩下所有的进行对比for(int j=i+1; j<arr.length;i++){if(arr[LeiZhu] > arr[j){//只需要记录下标，这样可以减少比较赋值的次数，降低复杂度LeiZhu = j;}}int temp = arr[LeiZhu];arr[LeiZhu] = arr[i];arr[i] = temp;
}

04 选择排序—堆排序

05 交换排序—冒泡排序

//外循环控制 总共遍历几次
for(int i=0; i<arr.length-1;i++){//内循环控制 一次循环遍历的过程for(int j=0; j<arr.length-i-1; j++){//每次遍历都是从头开始if(a[j]  > a[j+1]){temp = a[j];a[j] = a[j+1];a[j+1] = temp;}}
}

06 交换排序—快速排序

递归思路：

1. 选中povit位置的元素，让array[povit]作为分界线，array[povit]右边的元素均大于array[povit]值，左边的元素均大于array[povit]的值
2. 让povit作为分界线，开始判断从povit开始到数据末尾的快速排序 [array, povit+1, array.length-1]
3. 让povit作为分界线，开始判断从数据开头到povit的快速排序[array, 0, povit-1];

单个递归内部细节：

1. 选择一个povit作为基础元素
2. 令left指向数组的第一个元素， right指向最后一个元素
3. 从right开始进行判断：
   如果array[right]大于或者等于array[povit]成立: right = right-1;
   否则，right停止，执行步骤d
4. 从left开始进行判断：
   如果array[left]小于或者等于array[povit]成立： left = left + 1;
   否则，left停止，执行步骤e
5. 交换array[right]和array[left]两个元素的位置，然后继续执行步骤c
6. 直至left == right时结束，此时交换array[povit]和array[left]两个元素的位置

    public static void quickSort(int[] arr, int startIndex, int endIndex) {// 递归结束条件：startIndex大等于endIndex的时候if (startIndex >= endIndex) {return;}// 得到基准元素位置int pivotIndex = partition(arr, startIndex, endIndex);// 根据基准元素，分成两部分递归排序quickSort(arr, startIndex, pivotIndex - 1);quickSort(arr, pivotIndex + 1, endIndex);}private static int partition(int[] arr, int startIndex, int endIndex) {// 取第一个位置的元素作为基准元素int pivot = arr[startIndex];int left = startIndex;int right = endIndex;while( left != right) {//控制right指针比较并左移while(left<right && arr[right] > pivot){right--;}//控制right指针比较并右移while( left<right && arr[left] <= pivot) {left++;}//交换left和right指向的元素if(left<right) {int p = arr[left];arr[left] = arr[right];arr[right] = p;}}//pivot和指针重合点交换int p = arr[left];arr[left] = arr[startIndex];arr[startIndex] = p;return left;}public static void main(String[] args) {int[] arr = new int[] {4,7,6,5,3,2,8,1};quickSort(arr, 0, arr.length-1);System.out.println(Arrays.toString(arr));}

07 归并排序

思路：
1 ‘归’： 利用递归的分解数列
2 ‘并’： 合并数列
public void mergearray(int arr[], int left, int mid, int right, int temp[]){int i = left; int j = mid+1;int k = 0; while(i <= mid && j<=right){//两个有序数组进行比较，取小的那个if(arr[i] > arr[j]){temp[k++] = arr[j++];}else{temp[k++] = arr[i++];}//当右边序列走完了，左边剩下全放上去while(i<=mid){temp[k++] = arr[i++];}//当左边序列走完了，右边剩下全放上去while(j<mid){temp[k++] = arr[j++]}		for(int i=0; i<k; i++){arr[first+i] = temp[i];}}
}
public void mergesort(int arr[], int left, int right, int temp[]){if(right>left){int mid = (left+right)/2;//递归分解左边序列mergesort(arr, left, mid, temp)//递归分解右边序列mergesort(arr, mid+1, right, temp)//合并数列mergearray(arr, left, mid, right, temp)}
}

08 基数排序