潍坊学网站建设,互联网大数据精准营销,专业素材网站,优质网站建设公司哪家好1、插入排序
解析#xff1a;第一个元素设定为已经排好序#xff0c;依次选择后续的元素插入到已经排好序的组内进行排序。
图示#xff1a; 代码#xff1a;
public static void insertionSort(int[] arr) {int n arr.length;for (int i 1; i n; i) {int key a…1、插入排序
解析第一个元素设定为已经排好序依次选择后续的元素插入到已经排好序的组内进行排序。
图示 代码
public static void insertionSort(int[] arr) {int n arr.length;for (int i 1; i n; i) {int key arr[i];int j i - 1;// 将比当前元素大的元素向右移动while (j 0 arr[j] key) {arr[j 1] arr[j];j--;}// 插入当前元素到正确的位置arr[j 1] key;}} 时间复杂度最坏情况下为O(N^2)此时待排序列为逆序或者说接近逆序 最好情况下为O(N)此时待排序列为升序或者说接近升序。 空间复杂度O(1) 2、选择比较排序
解析每次从待排序列中选出一个最小值然后放在序列的起始位置直到全部待排数据排完。
图示 代码
public static void selectionSort(int[] arr) {int n arr.length;for (int i 0; i n - 1; i) {int minIndex i;// 寻找未排序部分的最小元素的索引for (int j i 1; j n; j) {if (arr[j] arr[minIndex]) {minIndex j;}}// 将找到的最小元素与未排序部分的第一个元素交换int temp arr[i];arr[i] arr[minIndex];arr[minIndex] temp;}} 时间复杂度最坏情况O(N^2) 最好情况O(N^2) 空间复杂度O(1) 3、冒泡排序
解析左边大于右边交换一趟排下来最大的在右边
图示 代码
public static void bubbleSort(int[] arr) {int n arr.length;for (int i 0; i n - 1; i) {for (int j 0; j n - i - 1; j) {if (arr[j] arr[j 1]) {// 交换arr[j]和arr[j 1]int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}}} 时间复杂度最坏情况O(N^2) 最好情况O(N) 空间复杂度O(1) 4、快排
解析
1先从数列中取出一个数作为基准数。2分区过程将比这个数大的数全放到它的右边小于或等于它的数全放到它的左边。3再对左右区间重复第二步直到各区间只有一个数或者这个区间不存在。
图示 代码
public static void quickSort(int[] arr, int low, int high) {if (low high) {// 划分数组返回分区点的索引int pivotIndex partition(arr, low, high);// 递归排序分区左侧和右侧的子数组quickSort(arr, low, pivotIndex - 1);quickSort(arr, pivotIndex 1, high);}}public static int partition(int[] arr, int low, int high) {int pivot arr[high]; // 选择最后一个元素作为基准元素int i low - 1;for (int j low; j high; j) {if (arr[j] pivot) {i;// 交换arr[i]和arr[j]int temp arr[i];arr[i] arr[j];arr[j] temp;}}// 将基准元素放到正确的位置int temp arr[i 1];arr[i 1] arr[high];arr[high] temp;return i 1;} 时间复杂度O(NlogN) 空间复杂度O(1) 5、希尔排序
解析
1.先选定一个小于N的整数gap作为第一增量然后将所有距离为gap的元素分在同一组并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量重复上述操作… 2.当增量的大小减到1时就相当于整个序列被分到一组进行一次直接插入排序排序完成。
图示 代码
public static void shellSort(int[] arr) {int n arr.length;// 初始间隔设为数组长度的一半然后逐渐缩小间隔for (int gap n / 2; gap 0; gap / 2) {for (int i gap; i n; i) {int temp arr[i];int j;for (j i; j gap arr[j - gap] temp; j - gap) {arr[j] arr[j - gap];}arr[j] temp;}}} 时间复杂度平均O(N) 空间复杂度O(1) 6、归并排序
解析
将待排序的线性表不断地切分成若干个子表直到每个子表只包含一个元素这时可以认为只包含一个元素的子表是有序表。将子表两两合并每合并一次就会产生一个新的且更长的有序表重复这一步骤直到最后只剩下一个子表这个子表就是排好序的线性表
图示 代码
public static void mergeSort(int[] arr) {int n arr.length;if (n 1) {return; // 如果数组长度小于等于1无需排序}// 将数组分成两个子数组int mid n / 2;int[] left new int[mid];int[] right new int[n - mid];System.arraycopy(arr, 0, left, 0, mid);System.arraycopy(arr, mid, right, 0, n - mid);// 递归排序左右子数组mergeSort(left);mergeSort(right);// 合并两个有序子数组merge(arr, left, right);}public static void merge(int[] arr, int[] left, int[] right) {int n1 left.length;int n2 right.length;int i 0, j 0, k 0;while (i n1 j n2) {if (left[i] right[j]) {arr[k] left[i];i;} else {arr[k] right[j];j;}k;}while (i n1) {arr[k] left[i];i;k;}while (j n2) {arr[k] right[j];j;k;}} 时间复杂度平均O(N) 空间复杂度O(N)
