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很可能减少到-1
int 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 交换排序—快速排序
递归思路：
- 选中povit位置的元素，让array[povit]作为分界线，array[povit]右边的元素均大于array[povit]值，左边的元素均大于array[povit]的值
- 让povit作为分界线，开始判断从povit开始到数据末尾的快速排序 [array, povit+1, array.length-1]
- 让povit作为分界线，开始判断从数据开头到povit的快速排序[array, 0, povit-1];
单个递归内部细节：
- 选择一个povit作为基础元素
- 令left指向数组的第一个元素， right指向最后一个元素
- 从right开始进行判断：
如果array[right]大于或者等于array[povit]成立: right = right-1;
否则，right停止，执行步骤d - 从left开始进行判断：
如果array[left]小于或者等于array[povit]成立： left = left + 1;
否则，left停止，执行步骤e - 交换array[right]和array[left]两个元素的位置，然后继续执行步骤c
- 直至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 基数排序
