网站建设站点地图wordpress怎么使用插件下载

当前位置： 首页 > news >正文

网站建设站点地图,wordpress怎么使用插件下载,湖南省建设工程造价管理总站网站,怎么查网站的所有权目录 一、插入排序

1. 直接插入排序
2. 希尔排序 二、选择排序
3. 直接选择排序 2. 堆排序 三、交换排序
4. 冒泡排序 2. 快速排序 四、归并排序 五、总结 一、插入排序
5. 直接插入排序 抓一张牌#xff0c;在有序的牌中#xff0c;找到合适的位置并且插入。 时间…目录 一、插入排序 1. 直接插入排序 2. 希尔排序 二、选择排序 1. 直接选择排序 2. 堆排序 三、交换排序 1. 冒泡排序 2. 快速排序 四、归并排序 五、总结 一、插入排序 1. 直接插入排序 抓一张牌在有序的牌中找到合适的位置并且插入。 时间复杂度O(n^2)空间复杂度O(1)稳定性稳定代码 public static void insertSort(long[] array) {for (int i 1; i array.length; i) {//认为第一个数已经有序所以循环 n - 1 次long tmp array[i];int j i - 1;for(; j 0; j–) {if (array[j] tmp) {array[j 1] array[j];} else {break;}}//j回退到了 小于0 的地方array[j 1] tmp;}} 2. 希尔排序 插入排序的升级版本即进行大量的分组插排。 时间复杂度O(n^1.3 ~ n^1.5)空间复杂度O(1)稳定性不稳定代码 //gap组数public static void shell (int[] array, int gap) {for (int i gap; i array.length; i) {int tmp array[i];int j i - gap;for (; j 0; j j - gap) {if (array[j] tmp) {array[j gap] array[j];} else {break;}}array[j gap] tmp;}}public static void shellSort(int[] array) {int gap array.length;while (gap 1) {shell(array,gap);gap gap / 2;}shell(array, 1);}二、选择排序 1. 直接选择排序 找到无序区间中最小的元素的下标然后将该元素放到无序区间的开始有序区间的最后。 时间复杂度O(n^2)空间复杂度O(1)稳定性不稳定 代码 // array: 待排序区间public static void selectSort(int[] array) {for (int i 0; i array.length; i) {int minIdx i;for (int j i 1; j array.length; j) {if (array[j] array[i]) {minIdx j;}}swap(array, minIdx, i);}} 2. 堆排序 选择排序的升级版本。将无序区间维护成一个大堆因为从小到达排序需要大堆。利用大堆从无序区间中找到最大值交换。 时间复杂度O( N*log(N))空间复杂度O(1)稳定性不稳定代码 //堆排序public static void heapSort(int[] array) {//1.建堆 O(n)creatHeap(array);int end array.length - 1;//2.交换然后调整 O(n * log(n))while (end 0) {swap(array, 0, end);shiftDown(array, 0, end);end–;}}public static void creatHeap(int[] array) {for (int parent (array.length - 1 - 1)/ 2; parent 0; parent–) {shiftDown(array, parent, array.length);}}public static void shiftDown(int[] array, int parent, int len) {int child 2 * parent 1; //左孩子下标while (child len) {if (child 1 len array[child] array[child 1]) {child;}//child 下标为左右孩子中最大的孩子的下标if (array[child] array[parent]) {swap(array, parent, child);parent child;child 2 * parent 1;} else {break;}}} 三、交换排序 1. 冒泡排序 从前往后两两元素进行比较前者大于后者则交换。每次循环完一个元素后面的有序区间就多加一个元素。 时间复杂度O(N^2)有序情况下O(n)空间复杂度O(1)稳定性稳定代码 public static void bubbleSort(int[] array) {for (int i 0; i array.length - 1; i) {boolean flag false;for (int j 0; j array.length - 1 - i; j) {if (array[j 1] array[j]) {swap(array, j, j 1);flag true;}}if (flag false) {break;}}} 2. 快速排序 ①在待排序区间内选择一个基准值pivot本次代码中选择的是最右边 ②对待排序区间进行 partition 操作目标将待排序区间分开左边的小于等于pivot右边的大于等于pivot ③分别再对左右两个小区间按照相同的方式进行处理。 时间复杂度     最好【每次可以均匀的分割待排序序列】O(N*log(N))     最坏数据有序 或者逆序的情况  O(N^2)空间复杂度     最好O(logN)     最坏O(n)   单分支的一棵树稳定性不稳定代码  public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}public static void quick(int[] array, int left, int right) {if (left right) {return;}int pivot partition(array, left, right);quick(array, left, pivot - 1);quick(array, pivot 1, right);}//挖坑法public static int partition(int[] array, int start, int end) {int tmp array[start];while (start end) {while(start end array[end] tmp) {end–;}//end位置的元素小于基准值挖坑array[start] array[end];while(start end array[start] tmp) {start;}//start位置的元素大于基准值挖坑array[end] array[start];}array[start] tmp;return start;} 由于用到了递归当基准值左右边已经有序时还需要栈空间来进行递归所以当数据过大时可能会导致栈溢出的情况所以要将快速排序进行优化。 当待排序区间元素个数小于某个范围时可以使用插入排序。找基准值时采用三数取中法。 代码  public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}public static void quick(int[] array, int left, int right) {if (left right) {return;}//优化1元素小于某个区间时使用插入排序if (right - left 1 1400) {insertSort(array, left, right);}//优化2三数取中法int MinIdx FindMinIdx(array, left, right);swap(array, MinIdx, left);int pivot partition(array, left, right);quick(array, left, pivot - 1);quick(array, pivot 1, right);}//挖坑法public static int partition(int[] array, int start, int end) {int tmp array[start];while (start end) {while(start end array[end] tmp) {end–;}//end位置的元素小于基准值挖坑array[start] array[end];while(start end array[start] tmp) {start;}//start位置的元素大于基准值挖坑array[end] array[start];}array[start] tmp;return start;}//插入排序public static void insertSort(int[] array, int start, int end) {for (int i 1; i end; i) {int tmp array[i];int j i - 1;for (; j start; j–) {if (array[j] tmp) {array[j 1] array[j];} else {//array[j 1] tmpbreak;}}// j 回退到了小于 0 的位置//或者从 break 出来array[j 1] tmp;}}//三数取中法private static int FindMinIdx(int[] array, int start, int end) {int mid start ((end - start) 1);if (array[start] array[end]) {if (array[mid] array[start]) {return start;} else if (array[mid] array[end]) {return end;} else {return mid;}} else {if (array[mid] array[start]) {return start;} else if (array[mid] array[end]) {return end;} else {return mid;}}}public static void swap(int[] array, int p, int q) {int tmp array[p];array[p] array[q];array[q] tmp;} 快速排序非递归版本利用栈存储 left 和 right 的值。 public static void quickSort非递归(int[] array) {DequeInteger stack new LinkedList();int left 0;int right array.length - 1;int pivot partition(array, left, right);if (pivot left 1) {//左边有两位数stack.push(left);stack.push(pivot - 1);}if (pivot right - 1) {stack.push(pivot 1);stack.push(right);}while(!stack.isEmpty()) {right stack.pop();left stack.pop();pivot partition(array, left, right);if (pivot left 1) {//左边有两位数stack.push(left);stack.push(pivot - 1);}if (pivot right - 1) {stack.push(pivot 1);stack.push(right);}}} 四、归并排序 归并排序是采用分治法的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 时间复杂度O(N*log(N))空间复杂度O(n)稳定性稳定在写归并排序代码之前需要先会写两个有序数组合并为一个有序数组。 代码 //将两个有序数组合并为一个有序数组//array1 和 array2 均为有序数组public static int[] mergeArray(int[] array1, int[] array2) {int[] tmp new int[array1.length array2.length];int s1 0;int s2 0;int e1 array1.length - 1;int e2 array2.length - 1;int k 0;while (s1 e1 s2 e2){if (array1[s1] array2[s2]) {tmp[k] array1[s1];//k;//s1} else {tmp[k] array2[s2];}}while (s1 e1) {tmp[k] array1[s1];}while (s2 e2) {tmp[k] array2[s2];}return tmp;} 归并排序代码 public static void mergeSort(int[] array) {mergeSortInternal(array, 0, array.length - 1);}private static void mergeSortInternal(int[] array, int low, int high) {if (low high) {return;}int mid low ((high - low) 1);mergeSortInternal(array, low, mid);mergeSortInternal(array, mid 1, high);merge(array, low, mid, high);}public static void merge(int[] array, int low, int mid, int high) {int[] tmp new int[high - low 1];int k 0;int s1 low;int e1 mid;int s2 mid 1;int e2 high;while (s1 e1 s2 e2) {if (array[s1] array[s2]) {tmp[k] array[s1];} else {tmp[k] array[s2];}}while (s1 e1) {tmp[k] array[s1];}while (s2 e2) {tmp[k] array[s2];}//普通的归并数组需要直接返回 tmp 数组//但是在归并排序中要将 tmp 数组重新拷贝到 array 数组中//并且考虑在右子树中合并时不能覆盖左边已经合并好的元素for (int i 0; i k; i) {array[low i] tmp[i];}} 非递归版本 public static void mergeSort非递归(int[] array) {int nums 1; //每组的数据个数while (nums array.length) {for (int i 0; i array.length; i) {int left i;int mid left nums - 1;//防止越界if (mid array.length) {mid array.length - 1;}int right mid nums;//防止越界if (right array.length) {right array.length - 1;}//下标确定之后进行合并merge(array, left, mid, right);}nums * 2;}} 五、总结 七大排序中 稳定的排序冒泡排序、插入排序、归并排序 插入排序主要看数组是否有序来影响其时间复杂度 归并排序无论什么情况下时间复杂度都为 O(N*log(N)) 时间复杂度为O(N*log(N))的排序快速排序、堆排序、归并排序 要想速度快就选 快速排序 要想稳定就选 归并 要想空间复杂度低就选 堆排序 排序时间复杂度空间复杂度稳定性插入排序O(N^2)O(1)稳定希尔排序O(N^1.3)O(1)不稳定选择排序O(N^2)O(1)不稳定堆排序O(N*log(N))O(1)不稳定冒泡排序O(N^2)O(1)稳定快速排序O(N*log(N))O(log(N))不稳定归并排序O(N*log(N)) O(n) 稳定