济南网站建设公司官网,如何自己创建网址,网站注册协议,最容易做的门户网站1.希尔排序-Shell Sort 1.算法原理 将未排序序列按照增量gap的不同分割为若干个子序列#xff0c;然后分别进行插入排序#xff0c;得到若干组排好序的序列#xff1b; 缩小增量gap#xff0c;并对分割为的子序列进行插入排序#xff1b;最后一次的gap1#xff0c;即整个… 1.希尔排序-Shell Sort 1.算法原理 将未排序序列按照增量gap的不同分割为若干个子序列然后分别进行插入排序得到若干组排好序的序列 缩小增量gap并对分割为的子序列进行插入排序最后一次的gap1即整个序列但此时已经基本有序对整个序列使用插入排序得到最终排好序的序列 公式表示gap{n/2(n/2)/2...1} {t1t2...tk} 即一共排序k次增量gap称作希尔增量
算法图解可以参考以下两种 2.算法复杂度
时间复杂度最优复杂度O(nlogn)最差复杂度O(n2)平均复杂度O(nlogn)
空间复杂度O(1)
3.算法实现-Java
public int[] shellSort(int[] arr){int len arr.length;int gap len / 2;while(gap 0){for(int i gap; i len; i){int currentValue arr[i];int preIndex i - gap;while(preIndex 0 arr[preIndex] currentValue){arr[preIndex gap] arr[preIndex];preIndex - gap;}arr[preIndex gap] currentValue;}gap gap / 2;}return arr;
} 2.归并排序-Merge Sort 1.算法原理 将未排序序列的所有元素分为若干组每个元素为一组将每组元素进行两两合并合并时按照从小到大或者从大到小对元素进行排序排序时比较每一组元素的头部即可重复此步骤直到最终只剩下一组数据则排序完成
2.算法复杂度
时间复杂度最优复杂度O(nlogn)最差复杂度O(nlogn)平均复杂度O(nlogn)
空间复杂度O(1)
3.算法实现-Java
public class MergeSort {public static void main(String[] args) {int[] a {9, 6, 2, 3, 7, 4, 8, 510};int L 0;int R a.length - 1;mergSort(a, L, R);System.out.println(Arrays.toString(a));}static void mergSort(int[] arr, int L, int R) {//只有一个数直接返回if (L R) {return;} else {int M (L R) / 2;mergSort(arr, L, M);mergSort(arr, M 1, R);merge(arr, L, M 1, R);}}static void merge(int[] arr, int L, int M, int R) {int left_size M - L;int right_size R - M 1;int[] L_arr new int[left_size];int[] R_arr new int[right_size];// 1 填充左边的数组for (int i L; i M; i) {L_arr[i - L] arr[i];}// 2 填充右边的数组for (int i M; i R; i) {R_arr[i - M] arr[i];}// 3 合并int i 0, j 0, k L;while (i left_size j right_size) {if (L_arr[i] R_arr[j]) {arr[k] R_arr[j];k;j;} else {arr[k] L_arr[i];i;k;}}// 4 若右边数组已空,把剩余左边数组补上while (i left_size) {arr[k] L_arr[i];i;k;}// 5 若左边数组已空,同上while (j right_size) {arr[k] R_arr[j];k;j;}}
} 3.快速排序-Quick Sort 1.算法原理 在未排序的序列中选择一个数作为基准一般选择序列的第一个数序列的最左侧和最右侧设置两个指针L和R 其中L从左往右移动R从右往左移动 首先R从右向左移动一位若指向的元素小于大于基准则将其移动到序列的最左边最右边然后L从左向右移动一位指向的元素与基准比较后执行相同操作 直到L与R移动到同一位置说明第一次排序完成此时相遇的位置就是基准元素的位置 接下来在基准的左右两边序列各选一个基准执行上述操作直到排序完成
2.算法复杂度
时间复杂度最优复杂度O(nlogn)最差复杂度O(nlogn)平均复杂度O(nlogn)
空间复杂度O(1)
3.算法实现-Java public static void quickSort(int[] arr,int low,int high){int i,j,temp,t;if(low high){return;}i low;j high;//temp为基准元素temp arr[low];while (i j) {//右边依次往左递减while (temp arr[j] i j) {j--;}//左边依次往右递增while (temp arr[i] i j) {i;}//如果满足条件则交换if (i j) {t arr[j];arr[j] arr[i];arr[i] t;}}//最后将基准为与i和j相等位置的数字交换arr[low] arr[i];arr[i] temp;//递归调用左半数组quickSort(arr, low, j-1);//递归调用右半数组quickSort(arr, j1, high);}
