学什么可以做响应式网站,普洱北京网站建设,网站seo关键字优化,软件优化今天我们带来数据结构中常见的8大排序算法。 排序算法平均时间复杂度最好情况最坏情况空间复杂度稳定性冒泡排序O(n方)O(n方)O(n方)O(1)稳定插入排序O(n方)O(n方)O(n方)O(1)稳定选择排序O(n方)O(n方)O(n方)O(1)不稳定希尔排序O(n1.3方到1,5方)O(n)O(n方)O(1)不稳定堆排序O(n lo… 今天我们带来数据结构中常见的8大排序算法。 排序算法平均时间复杂度最好情况最坏情况空间复杂度稳定性冒泡排序O(n方)O(n方)O(n方)O(1)稳定插入排序O(n方)O(n方)O(n方)O(1)稳定选择排序O(n方)O(n方)O(n方)O(1)不稳定希尔排序O(n1.3方到1,5方)O(n)O(n方)O(1)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定快速排序O(n log n)O(n log n) O(n方) O(n log n)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定计数排序O(n k)O(n k)O(n k)O(k)不稳定 一冒泡排序 思路1从头到尾比较相邻的元素2重复第一步n-1次 代码实现
public void BubbleSort(int[] array){int[] str Arrays.copyOf(array,array.length);for (int i 0; i str.length; i) {for (int j 0; j str.length-1-i; j) {if(str[j]str[j1]){swap(str,j,j1);}}}System.out.println(Arrays.toString(str));}
swap是交换
private void swap(int[] str,int i,int j){int tmp str[i];str[i] str[j];str[j] tmp;}
代码优化 优化也不会优化到多好基本还是O(n方的复杂度) public void BubbleSortLevel(int[] array){int[] str Arrays.copyOf(array,array.length);for (int i 0; i str.length; i) {boolean a false;for (int j 0; j str.length-1-i; j) {if(str[j]str[j1]){swap(str,j,j1);a true;}}if(!a){break;}}System.out.println(Arrays.toString(str));}
二插入排序 思路 1定义两个下标i,jtmpi从1开始向后遍历把初始的下标值赋给tmp 2j每次从i前面开始向前遍历比较j下标的元素和tmp的值。 代码实现
public void InsertSort(int[] array){int[] str Arrays.copyOf(array,array.length);int j0;int tmp0;for (int i 1; i str.length; i) {tmp str[i];for (j i-1; j 0 ; j--) {if(str[j]tmp){str[j1] str[j];}else {break;}}str[j1] tmp;}System.out.println(Arrays.toString(str));}
三选择排序 思路 1定义两个下标iji从左向右遍历2我们创建一个tmpIndex记录i下标的值j每次都在i的左边与tmpIndex的值进行比较记录新的tmpIndex的值与i下标交换重复这个步骤。 代码实现
public void ChooseSort(int[] array){int[] str Arrays.copyOf(array,array.length);int j 0;int tmpIndex 0;for (int i 0; i str.length; i) {tmpIndex i;for (j i1; j str.length; j) {if(str[j]str[tmpIndex]){tmpIndex j;}}swap(str,i,tmpIndex);}System.out.println(Arrays.toString(str));}
四希尔排序 思路 希尔排序实际就是多次进行快速排序但是我们每次是不同的几组数进行排序我们初始一个gapgap的取值不一我们一数组长度/2来赋给gap,每次相邻为gap的元素进行插入排序再对gap/2直到gap为1我们的思路是插入排序对越有序的数组排序越有序 代码实现 public void ShellSort(int[] array){int[] str Arrays.copyOf(array,array.length);int gap str.length/2;while (gap1){ShellSort__InsertSort(str,gap);gap/2;}System.out.println(Arrays.toString(str));}private void ShellSort__InsertSort(int[] str,int gap){int tmp 0;int j 0;for (int i gap; i str.length; i) {tmp str[i];for (j i-gap; j 0; j-gap) {if(str[j]tmp){str[jgap] str[j];}else {break;}}str[jgap] tmp;}}
五堆排序 思路 以升序为例降序建小根堆升序建大根堆 1建堆 2栈顶元素与尾元素互换再进行向下调整 3直到重复步骤2直到0下标。 代码实现
public void HeapSort(int[] array){int[] str Arrays.copyOf(array,array.length);CreateHeap(str);for (int i str.length-1; i 0 ; i--) {swap(str,i,0);ShiftDown(str,0,i);}System.out.println(Arrays.toString(str));}private void CreateHeap(int[] str){int c str.length-1;int p (c-1)/2;while (p0){ShiftDown(str,p,str.length);p--;}System.out.println(Arrays.toString(str));}private void ShiftDown(int[] str, int parent,int usdSize){int child 2*parent1;while (childusdSize){if(child1usdSize str[child]str[child1]){child;}if(str[child]str[parent]){swap(str,child,parent);parent child;child 2*parent1;}else {break;}}}
六快速排序 思路 1选择一个基准定义两个下标一个从右往左走先走一个从左往右走右边遇到小于基准的与左边大于基准的交换 2找到基准从基准左边和右边递归重复1的过程。 代码实现递归实现
public void QuickSort(int[] array){int[] str Arrays.copyOf(array,array.length);QuickSortChild(str,0,str.length-1);System.out.println(Arrays.toString(str));}private void QuickSortChild(int[] str,int start,int end){if(startend){return;}int left start;int right end;int part partition(str,left,right);QuickSortChild(str,start,part-1);QuickSortChild(str,part1,end);}private int partition(int[] str,int start,int end){int left start;int right end;int cmp str[left];while (leftright){while (leftright str[right]cmp){right--;}while (leftright str[left]cmp){left;}if(leftright){swap(str,left,right);}}swap(str,start,left);return left;}
代码优化递归实现三数取中法
public void QuickSort2(int[] array){int[] str Arrays.copyOf(array,array.length);QuickSortChild(str,0,str.length-1);System.out.println(Arrays.toString(str));}private void QuickSortChild2(int[] str,int start,int end){if(startend){return;}int left start;int right end;int mid middle(left,(leftright)/2,right);swap(str,start,mid);int part partition(str,left,right);QuickSortChild(str,start,part-1);QuickSortChild(str,part1,end);}private int partition2(int[] str,int start,int end){int left start;int right end;int cmp str[left];while (leftright){while (leftright str[right]cmp){right--;}while (leftright str[left]cmp){left;}if(leftright){swap(str,left,right);}}swap(str,start,left);return left;}private int middle(int left,int middle,int right){int[] arr new int[]{left,middle,right};Arrays.sort(arr);return arr[1];} 代码实现非递归实现
public void QuickSort3(int[] array){int[] str Arrays.copyOf(array,array.length);QuickSortChild3(str,0,array.length-1);System.out.println(Arrays.toString(str));}private void QuickSortChild3(int[] str,int start,int end){DequeInteger stack new ArrayDeque();int part partition3(str,start,end);if (part1end){stack.push(end);stack.push(part1);}if(part-1start){stack.push(part-1);stack.push(start);}while (!stack.isEmpty()){end stack.pop();start stack.pop();part partition3(str,start,end);if (part1end){stack.push(end);stack.push(part1);}if(part-1start){stack.push(part-1);stack.push(start);}}}private int partition3(int[] str,int start,int end){int left start;int right end;int cmp str[left];while (leftright){while (leftright str[right]cmp){right--;}while (leftright str[left]cmp){left;}if(leftright){swap(str,left,right);}}swap(str,start,left);return left;} 七归并排序 思路 1我们把数据平均分为两个部分定义左中右三个下标左边递归右边递归 2当左下标大于等于右递下标归停止我们使用合并数组的方法把每层递归后有序的左右子树有序化 代码实现
public void MergeSort(int[] array){int[] str Arrays.copyOf(array,array.length);MergeSortChild(str,0,str.length-1);System.out.println(Arrays.toString(str));}private void MergeSortChild(int[] str,int left, int right){if(leftright){return;}int mid (leftright)/2;MergeSortChild(str,left,mid);MergeSortChild(str,mid1,right);MergeSort__new(str,left,mid,right);}private void MergeSort__new(int[] str,int left,int mid,int right){int s1 left;int e1 mid;int s2 mid1;int e2 right;int[] arr new int[right-left1];int i0;while (s1e1 s2e2){if(str[s1]str[s2]){arr[i] str[s1];i;s1;}if(str[s2]str[s1]){arr[i] str[s2];i;s2;}}while (s1e1){arr[i] str[s1];i;s1;}while (s2e2){arr[i] str[s2];i;s2;}for (int k 0; k i; k) {str[kleft] arr[k];}} 八计数排序
计数排序适合排那些一定范围的大量数据比如1-100的考试成绩 思路 1我们遍历原数组找出最大值最小值用他们的差值大小构建一个计数数组 2把原数组出现的数字-min放到计数数组里有一个计数数组就加一循环遍历计数数组直到计数数组全部元素都为0 代码实现
public void CountIngSort(int[] array){int[] str Arrays.copyOf(array,array.length);int max str[0];int min str[0];for (int i 0; i str.length ; i) {if(str[i]max){max str[i];}if(str[i]min){min str[i];}}int[] count new int[max-min1];for (int i 0; i str.length; i) {int a str[i];count[a-min]1;}int j 0;int i 0;while (icount.length) {while (count[i]!0){str[j] imin;j;count[i]--;}i;}System.out.println(Arrays.toString(str));}
