爱用建站正规吗淘宝网发布网站建设

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

爱用建站正规吗,淘宝网发布网站建设,昆明 网站 制作,网站建设与制专栏#xff1a;Java数据结构秘籍 个人主页#xff1a;手握风云 目录 一、常见排序算法的实现 1.1. 直接选择排序 1.2. 堆排序 1.3. 冒泡排序 1.4. 快速排序 一、常见排序算法的实现 1.1. 直接选择排序 每⼀次从待排序的数据元素中选出最小的⼀个元素#xff0c;存放在… 专栏Java数据结构秘籍 个人主页手握风云 目录 一、常见排序算法的实现 1.1. 直接选择排序 1.2. 堆排序 1.3. 冒泡排序 1.4. 快速排序 一、常见排序算法的实现 1.1. 直接选择排序 每⼀次从待排序的数据元素中选出最小的⼀个元素存放在序列的起始位置直到全部待排序的数据元素排完。第一轮先让j下标遍历出数组中最小的元素再利用MinIndex存放最小的下标利用最小值与i下标的元素进行交换第二轮依然让j下标遍历出待排序中最小的元素再利用MinIndex存放最小的下标利用最小值与i下标的元素进行交换……知道i走到最后一个元素这样就能保证i之前的元素全部是有序的。 import java.util.Random;public class Sort {public void SelectSort(int[] array){for (int i 0; i array.length; i) {int MinIndex i;for (int j i1; j array.length; j) {if(array[MinIndex] array[j]){MinIndex j;}}swap(array,MinIndex,i);}}private void swap(int[] array,int i,int j){int tmp array[i];array[i] array[j];array[j] tmp;}public void DisOrder(int[] array) {Random ran new Random();for (int i 0; i array.length; i) {array[i] ran.nextInt(100);}} } import java.util.Arrays;public class Test {public static void main(String[] args) {int[] array new int[6];Sort sort new Sort();sort.DisOrder(array);System.out.println(排序前 Arrays.toString(array));sort.SelectSort(array);System.out.println(排序后Arrays.toString(array));} } 直接选择排序是不稳定的。空间上没有使用额外的空间空间复杂度为。时间上 直接选择排序还有另外一种思路。与上面的方法不同的是我们需要两个值MinIndex接收最小值下标和MaxIndex来接收最大值下标再额外定义两个指针left和right。这种选择排序的思路是从首尾找起始两个值接收下标都为0利用i去遍历数组找出最大值与最小值下标再让left下标的值与MinIndex下标的值交换right下标的值与MaxIndex下标的值交换。接着再让left向左移动right向右移动直到相遇循环结束 完整代码实现 import java.util.Random;public class Sort {public void DisOrder(int[] array) {Random ran new Random();for (int i 0; i array.length; i) {array[i] ran.nextInt(100);}}public void SelectSort(int[] array) {int left 0, right array.length - 1;while (left right) {int MinIndex left, MaxIndex left;for (int i left 1; i right; i) {if (array[i] array[MinIndex]) {MinIndex i;}if (array[i] array[MaxIndex]) {MaxIndex i;}}swap(array, MinIndex, left);swap(array, MaxIndex, right);left;right–;}}private void swap(int[] array, int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;} } import java.util.Arrays;public class Test {public static void main(String[] args) {Sort sort new Sort();int[] array new int[6];sort.DisOrder(array);System.out.println(排序前 Arrays.toString(array));sort.SelectSort(array);System.out.println(排序后 Arrays.toString(array));} } 但我们一运行就会发现排序出现了问题这是因为如果最大值或最小值本身就在首尾那么一交换最大值或最小值就会跑掉所以我们还需要判断一下。 import java.util.Random;public class Sort {public void DisOrder(int[] array) {Random ran new Random();for (int i 0; i array.length; i) {array[i] ran.nextInt(100);}}public void SelectSort(int[] array) {int left 0, right array.length - 1;while (left right) {int MinIndex left, MaxIndex left;for (int i left 1; i right; i) {if (array[i] array[MinIndex]) {MinIndex i;}if (array[i] array[MaxIndex]) {MaxIndex i;}}swap(array, MinIndex, left);/if (left MaxIndex) {MaxIndex MinIndex;}/swap(array, MaxIndex, right);left;right–;}}private void swap(int[] array, int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;} } import java.util.Arrays;public class Test {public static void main(String[] args) {Sort sort new Sort();int[] array new int[6];sort.DisOrder(array);System.out.println(排序前 Arrays.toString(array));sort.SelectSort(array);System.out.println(排序后 Arrays.toString(array));} } 1.2. 堆排序 堆排序是指利⽤堆积树这种数据结构所设计的⼀种排序算法它是选择排序的⼀ 种通过堆来进⾏选择数据。需要注意的是排升序要建大堆排降序建小堆。 import java.util.Random;public class Sort {public void HeapSort(int[] array) {CreateHeap(array);int end array.length - 1;while(end 0){swap(array,0,end);ShiftDown(array,0,end);end–;}}private void CreateHeap(int[] array) {for (int parent (array.length - 1 - 1) / 2; parent 0; parent–) {ShiftDown(array, parent, array.length);}}private void ShiftDown(int[] array, int parent, int length) {int child 2 * parent 1;while (child length) {if (child 1 length array[child] array[child 1]) {child;}if (array[child] array[parent]) {swap(array,parent,child);parent child;child 2 * parent 1;} else {break;}}}private void swap(int[] array,int i,int j){int tmp array[i];array[i] array[j];array[j] tmp;}public void DisOrder(int[] array){Random ran new Random();for (int i 0; i array.length; i) {array[i] ran.nextInt(1,100);}} } import java.util.Arrays;public class Solution {public static void main(String[] args) {Sort sort new Sort();int[] array new int[6];sort.DisOrder(array);System.out.println(排序前 Arrays.toString(array));sort.HeapSort(array);System.out.println(排序前 Arrays.toString(array));} } 堆排序使⽤堆来选数效率就⾼了很多。但堆排序是不稳定的时间复杂度为空间复杂度为。 1.3. 冒泡排序 定义下标j比较array[j]与array[j1]的值如果array[j] array[j1]则交换两数的位置。我们还可以进行一个优化如果数组本身就是有序或者没有走完所有的趟数就已经有序那么后面就不用再比较了。 import java.util.Random;public class Sort {public void DisOrder(int[] array) {Random ran new Random();for (int i 0; i array.length; i) {array[i] ran.nextInt(1, 100);}}public void BubbleSort(int[] array) {//表示交换的趟数for (int i 0; i array.length-1; i) {boolean flg false;for (int j 0; j array.length-1-i; j) {if(array[j] array[j1]){swap(array,j,j1);flg true;}}if(!flg){break;}}}private void swap(int[] array,int i,int j){int tmp array[i];array[i] array[j];array[j] tmp;} } import java.util.Arrays;public class Test {public static void main(String[] args) {Sort sort new Sort();int[] array new int[6];sort.DisOrder(array);System.out.println(排序前Arrays.toString(array));sort.BubbleSort(array);System.out.println(排序后Arrays.toString(array));} }冒泡排序是稳定的。时间复杂度空间复杂度。 1.4. 快速排序 快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法其基本思想为任取待排序元素 序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列。 我们需要定义两个指针left和right假设以6作为基准值left向左移动遇到比6大的数停下right向右移动遇到比6小的数停下然后交换两个元素。当两个指针相遇时再与基准值进行交换。这样就能保证6左边都是比6小的数6右边都是比6大的数。按照这个过程再次进行构成递归的条件直到分离出只含一个值的子序列。这样就构成了如下图所示的二叉树结构。 public class Sort {public void QuickSort(int[] array){}public void Quick(int[] array,int start,int end){if(start end){//如果结点的右子树为空就不用遍历右边return;}int par partition(array,start,end);Quick(array,start,par-1);Quick(array,par1,end);//当startend时递归条件结束}private int partition(int[] array, int left, int right) {return -1;} } 我们接下来要思考的问题是如何写partition这个方法。无论是递归左边还是右边与上面的过程都是一样的。只要left下标的值比基准值小left右移只要right下标的值比基准值大right右移。这里我们还需要注意里层的while循环指针不能越界。 private int partition(int[] array, int left, int right) {int i left;int tmp array[left];while(left right){while(left right array[right] tmp){right–;}while(left right array[left] tmp){left;}swap(array,left,right);}swap(array,left,i);return left;} 完整代码实现 import java.util.Random;public class Sort {public void DisOrder(int[] array){Random ran new Random();for (int i 0; i array.length; i) {array[i] ran.nextInt(1,40);}}public void QuickSort(int[] array){Quick(array,0,array.length-1);}public void Quick(int[] array,int start,int end){if(start end){//如果结点的右子树为空就不用遍历右边return;}int par partition(array,start,end);Quick(array,start,par-1);Quick(array,par1,end);//当startend时递归条件结束}private int partition(int[] array, int left, int right) {int i left;int tmp array[left];while(left right){while(left right array[right] tmp){right–;}while(left right array[left] tmp){left;}swap(array,left,right);}swap(array,left,i);return left;}private void swap(int[] array,int i,int j){int tmp array[i];array[i] array[j];array[j] tmp;} } import java.util.Arrays;public class Test {public static void main(String[] args) {Sort sort new Sort();int[] array new int[6];sort.DisOrder(array);System.out.println(排序前Arrays.toString(array));sort.QuickSort(array);System.out.println(排序后Arrays.toString(array));} }这里解释一下为什么先让right移动防止越过某些值。这里我们还需要注意或的等号不能省略如果left和right的值与基准值相等那么就不会进入内层的while循环导致外层的while循环陷入死循环。 快速排序是不稳定的。快速排序的时间复杂度通常是指最好情况下因为我们经常对快速排序进行优化。 快速排序还有一种做法——挖坑法。与上面的方法类似我们依然是以6为基准值把6存进tmp中right向左移动遇到比6小的数把6之前的位置填上left向右移动遇到比6大的数把5之前的位置填上……我们只需要对上面的代码进行修改就可以。 import java.util.Random;public class Sort {public void DisOrder(int[] array){Random ran new Random();for (int i 0; i array.length; i) {array[i] ran.nextInt(1,40);}}public void QuickSort(int[] array){Quick(array,0,array.length-1);}public void Quick(int[] array,int start,int end){if(start end){//如果结点的右子树为空就不用遍历右边return;}int par partition(array,start,end);Quick(array,start,par-1);Quick(array,par1,end);//当startend时递归条件结束}private int partition(int[] array, int left, int right) {int i left;int tmp array[left];while(left right){while(left right array[right] tmp){right–;}array[left] array[right];while(left right array[left] tmp){left;}array[right] array[left];}array[left] tmp;return left;}}import java.util.Arrays;public class Test {public static void main(String[] args) {Sort sort new Sort();int[] array new int[6];sort.DisOrder(array);System.out.println(排序前 Arrays.toString(array));sort.QuickSort(array);System.out.println(排序后 Arrays.toString(array));} } 我们接下来思考一下快排的优化。我们先来看第一种三数取中法。我们找出start和end的中位数让二叉树的形状尽量不要出现单分支的情况。那我们怎么再这段区间里面去找中位数呢我们可以通过下标来找 private static int midNum(int[] array, int left, int right) {int mid (leftright)/2;if(array[left] array[right]) {if(array[mid] array[left]) {return left;}else if(array[mid] array[right]) {return right;}else {return mid;}}else {if(array[mid] array[left]) {return left;}else if(array[mid] array[right]) {return right;}else {return mid;}}} 第二种递归到⼩的⼦区间时可以考虑使⽤插⼊排序。