🍌 希尔排序（Shell Sort）
简介：
1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
设计思想：
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
代码实现：
c语言版
void ShellSort(int *arr, int size) { int i, j, tmp, increment; for (increment = size/ 2; increment > 0; increment /= 2) { for (i = increment; i < size; i++) { tmp = arr[i]; for (j = i - increment; j >= 0 && tmp < arr[j]; j -= increment) { arr[j + increment] = arr[j]; } arr[j + increment] = tmp; } } }
Java版
/** * 希尔排序 * @param array * @return * @date 2022/01/20 */ public static int[] shellSort(int[] array){undefined if(array.length > 0){ int len = array.length; int gap = len / 2; while(gap > 0){undefined for(int i = gap;i < len;i++){undefined int temp = array[i]; int index = i - gap; while(index >= 0 && array[index] > temp){undefined array[index + gap] = array[index]; index -= gap; } array[index + gap] = temp; } gap /= 2; } } return array; }
🥒 归并排序（Merge Sort）
简介：
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer） 的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
设计思想：
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
代码实现：
c语言版
#define MAXSIZE 100 void Merge(int *SR, int *TR, int i, int middle, int rightend) { int j, k, l; for (k = i, j = middle + 1; i <= middle && j <= rightend; k++) { if (SR[i] < SR[j]) { TR[k] = SR[i++]; } else { TR[k] = SR[j++]; } } if (i <= middle) { for (l = 0; l <= middle - i; l++) { TR[k + l] = SR[i + l]; } } if (j <= rightend) { for (l = 0; l <= rightend - j; l++) { TR[k + l] = SR[j + l]; } } } void MergeSort(int *SR, int *TR1, int s, int t) { int middle; int TR2[MAXSIZE + 1]; if (s == t) { TR1[s] = SR[s]; } else { middle = (s + t) / 2; MergeSort(SR, TR2, s, middle); MergeSort(SR, TR2, middle + 1, t); Merge(TR2, TR1, s, middle, t); } }
Java
/** * 2路归并算法 * @param array * @return * @date 2022/01/20 */ public static int[] MergeSort(int[] array){ if(array.length < 2){ return array; } int mid = array.length /2; int[] left = Arrays.copyOfRange(array, 0, mid); int[] right = Arrays.copyOfRange(array, mid, array.length); return merge(MergeSort(left),MergeSort(right)); } public static int[] merge(int[] left,int[] right){ int[] result = new int[left.length + right.length]; for(int index = 0,i = 0, j = 0;index < result.length;index++){ if(i >= left.length){ result[index] = right[j++]; }else if(j >= right.length){ result[index] = left[i++]; }else if(left[i] > right[j]){ result[index] = right[j++]; }else{ result[index] = left[i++]; } } return result; }
