设计一个企业网站首页,wordpress更换域名所有页面404,安阳那里可以制作网站,沈阳网站的建设#x1f525;博客主页#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞#x1f44d;收藏⭐评论✍ 文章目录 1.0 实现冒泡排序 2.0 实现选择排序 2.1 选择排序的改良升级 3.0 实现堆排序 4.0 实现插入排序 5.0 实现希尔排序 6.0 实现归并排序 6.1 递归实现归并排序 6.2 使用… 博客主页 【小扳_-CSDN博客】 ❤感谢大家点赞收藏⭐评论✍ 文章目录 1.0 实现冒泡排序 2.0 实现选择排序 2.1 选择排序的改良升级 3.0 实现堆排序 4.0 实现插入排序 5.0 实现希尔排序 6.0 实现归并排序 6.1 递归实现归并排序 6.2 使用非递归实现归并排序 6.3 递归归并排序 插入排序 7.0 快速排序 7.1 单边循环快排 7.2 双边循环快排 7.3 快速排序的改良升级 1.0 实现冒泡排序 冒泡排序是一种简单的排序算法它重复地遍历要排序的列表比较相邻的元素并交换它们直到列表排序完成。冒泡排序的时间复杂度为 O(n^2) 在最坏的情况下需要进行 n*(n-1)/2 次比较和交换操作。是一个稳定排序。
具体步骤如下 -从列表的第一个元素开始依次比较相邻的两个元素如果它们的顺序不正确则交换它们的位置。 - 继续比较相邻的元素直到达到列表的末尾。 - 重复以上步骤直到列表排序完成。 冒泡排序的详解过程 冒泡排序的过程可以用一个简单的示意图来说明假设我们要对一个包含5个元素的列表进行冒泡排序 初始状态 [5, 3, 8, 2, 1] 第一轮冒泡比较相邻的元素并交换它们的位置直到最大的元素被“冒泡”到列表的末尾。[3, 5, 2, 1, 8] [x, x, x, x, 8] 所在的位置就是最终的位置因此不需要再进行交换了。 第二轮冒泡同样比较相邻的元素并交换它们的位置直到最大的元素被“冒泡”到列表的末尾。[3, 2, 1, 5, 8] [x, x, x, 5, 8] 所在的位置就是最终的位置因此不需要再进行交换了。 第三轮冒泡同理[2, 1, 3, 5, 8] , [x, x, 3, 5, 8] 所在的位置就是最终的位置因此不需要再进行交换了。 第四轮冒泡[1, 2, 3, 5, 8] 完成排序了一共需要进行数组长度 - 1 轮冒泡。 数组的顺序为 [87654321] 来进行冒泡排序的动态演示过程 代码如下 import java.util.Arrays;public class BubbleSort {public static void main(String[] args) {int[] arr {1,10,7,4,8,3,2,6,9,5};bubble(arr);System.out.println(Arrays.toString(arr));}//冒泡排序public static void bubble(int[] arr) {for (int i 0;i arr.length-1; i) {for (int j 0 ;j arr.length-1-i;j) {if (arr[j] arr[j1]) {int temp arr[j];arr[j] arr[j1];arr[j1] temp;}}}}
} 2.0 实现选择排序 选择排序Selection Sort是一种简单直观的排序算法。选择排序的时间复杂度为 O(n^2) 因为在每一轮中需要进行n次比较找到最小元素。默认从小到大排序 基本思想每次从待排序的数据元素中选出最小或最大的一个元素然后放到已排序序列的末尾。内层循环代表的是当前这次循环中需要找到剩余数组中最小的元素外层循坏代表的是需要进行多少次内层循环才能将数组中的元素按从小到大排序完成。 举例详解选择过程 初识状态[3, 44, 5, 27, 2, 50, 48] 第一轮选择过程记录未排好序的元素 3 然后从元素 3 的后一个元素 44 出发寻找比 3 小的元素如果找到了则需要进行交换如果没有找到这说明元素 3 就是当前循环过程中最小的元素。当前找到了比元素 3 小的元素 2 那么需要进行交换。 第二轮选择过程因为元素 2 已经排好序了那么需要记录从排好序元素的后一个元素 44 寻找的范围是当前记录的元素的后一个元素开始出发直到数组最后一个元素。同样重复以上操作如果找到了比 44 要小的元素需要进行记录 minIndex i 内层循环结束后最小的元素下标为 minIndex 交换 44 与下标为 minIndex 的元素。 第三轮选择过程也是一样流程这里就不多赘述了...... 选择过程的动态图演示过程 代码如下 import java.util.Arrays;public class SelectSort {public static void main(String[] args) {int[] arr {1,10,7,4,8,3,2,6,9,5};select1(arr);System.out.println(Arrays.toString(arr));}public static void select1(int[] arr) {for (int i 0;i arr.length - 1;i) {int minIndex i;for (int j i 1;j arr.length;j) {if (arr[j] arr[minIndex]) {minIndex j;}}if (i ! minIndex) {swap(arr,i,minIndex);}}}public static void swap(int[] arr,int i,int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}} 2.1 选择排序的改良升级 在选择过程中内层循环每一次都是寻找最小的元素这次改进是在寻找最小元素的同时又找最大的元素定义两个 letf ,right 指针一开始分别指向数组的左右两边。此时外层的循环条件left right 。一次内层循环中找到了最小、最大元素接着就分别于 left、right 下标元素进行交换交换完之后left right-- 。 一开始 minIndex、maxIndex 都是从 left 开始从左到右进行查找元素的。重点需要需要注意的是假如最大的元素就是当前的 left 下标时且 minIndex 与 left 进行交换后会导致 maxIndex 找的元素下标就会发生变化所以在下标 minIndex 与 left 交换完之后需要判断 maxInde left 是否发生如果发生了那么 maxIndex 需要重新赋值为 maxIndex minIndex 。
代码如下 import java.util.Arrays;public class SelectSort {public static void main(String[] args) {int[] arr {1,10,7,4,8,3,2,6,9,5};select2(arr);System.out.println(Arrays.toString(arr));}public static void swap(int[] arr,int i,int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}public static void select2(int[] arr) {int left 0;int right arr.length-1;while (left right) {int minIndex left;int maxIndex left;for (int i left1;i right; i) {if (arr[i] arr[minIndex]) {minIndex i;}if (arr[i] arr[maxIndex]) {maxIndex i;}}swap(arr,minIndex,left);if (maxIndex left) {maxIndex minIndex;}swap(arr,maxIndex,right);left;right--;}}} 3.0 实现堆排序 堆排序Heap Sort是一种高效的排序算法它利用了堆这种数据结构来实现排序。堆是一种特殊的完全二叉树分为最大堆和最小堆两种类型。在堆排序中通常使用最大堆。堆排序的时间复杂度为 O(nlogn) 并且是原地排序算法不需要额外的存储空间。 堆排序的基本思想首先将待排序的数据构建成一个最大堆然后将堆顶元素最大元素与堆的最后一个元素交换然后对剩余的元素重新调整为最大堆重复这个过程直到整个序列有序。 两个动作首先是将数组中的元素构建成一个大顶堆的形式接着从堆的最后一个元素与堆顶元素进行交换再对当前的堆顶元素进行下潜处理循环该过程即可。 堆排序的动态演示过程该过程演示的是降序的排序过程那么相反建立一个小顶堆 代码如下 建立大顶堆的代码下潜、交换元素 class Heap {int[] arr;int size 0;public Heap(int[] arr) {this.arr arr;this.size arr.length;buildBigHeap(arr,size);heapSort(arr);}public void buildBigHeap(int[] arr,int size) {for (int i size / 2 - 1; i 0 ; i--) {down(i,size);}}private void down(int i,int size) {int left i * 2 1;int right left 1;int max i;if (left size arr[max] arr[left]) {max left;}if (right size arr[max] arr[right]) {max right;}if (max ! i) {swap(arr,max,i);down(max,size);}}private void swap(int[] arr,int i,int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}} 堆排序的完整代码 import java.util.Arrays;public class HeapSort {public static void main(String[] args) {int[] arr {1,10,7,4,8,3,2,6,9,5};Heap heap new Heap(arr);System.out.println(Arrays.toString(arr));}
}
class Heap {int[] arr;int size 0;public Heap(int[] arr) {this.arr arr;this.size arr.length;buildBigHeap(arr,size);heapSort(arr);}public void buildBigHeap(int[] arr,int size) {for (int i size / 2 - 1; i 0 ; i--) {down(i,size);}}private void down(int i,int size) {int left i * 2 1;int right left 1;int max i;if (left size arr[max] arr[left]) {max left;}if (right size arr[max] arr[right]) {max right;}if (max ! i) {swap(arr,max,i);down(max,size);}}private void swap(int[] arr,int i,int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}public void heapSort(int[] arr) {for (int i arr.length - 1; i 0 ; i--) {swap(arr,i,0);down(0,i);}}} 4.0 实现插入排序 插入排序是一种简单直观的排序算法它的工作原理是通过构建有序序列对未排序的数据逐个进行插入从而达到排序的目的。插入排序的时间复杂度为 O(n^2) 在最坏情况下逆序排列的数组需要进行 n*(n-1)/2 次比较和交换操作。插入排序适用于小规模数据或部分有序的数据。是一个稳定排序。
具体来说插入排序的算法步骤如下 1.从第一个元素开始该元素可以认为已经被排序。 2.取出下一个元素在已经排序的元素序列中从后向前扫描。 3.如果该元素已排序大于新元素将该元素移到下一位置。 4.重复步骤3直到找到已排序的元素小于或等于新元素的位置。 5.将新元素插入到该位置后。 6.重复步骤2~5。 插入排序动态图演示过程 代码如下 import java.util.Arrays;public class InsertSort {public static void main(String[] args) {int[] arr {1,10,7,4,8,3,2,6,9,5};insert(arr);System.out.println(Arrays.toString(arr));}public static void insert(int[] arr) {for (int i 1; i arr.length; i) {int key arr[i];int j i - 1;while(j 0 arr[j] key) {arr[j1] arr[j];j--;}arr[j1] key;}}} 5.0 实现希尔排序 希尔排序Shell Sort是一种改进的插入排序算法也被称为“缩小增量排序”。它通过将数组分割成若干个子序列对每个子序列进行插入排序最终进行一次完整的插入排序得到有序序列。希尔排序的工作原理是通过逐步减小增量的方式最终达到增量为1的插入排序。希尔排序的时间复杂度取决于增量序列的选择通常为 O(n logn) 。
希尔排序的算法步骤如下 1. 选择一个增量序列通常为 n/2、n/4、n/8……直到增量为 1 。 2. 对每个增量进行插入排序即将数组分割成若干个子序列对每个子序列进行插入排序。 3. 逐步缩小增量重复步骤 2 直到增量为 1 。 4. 最后进行一次增量为 1 的插入排序完成排序过程。 希尔排序的动态演示过程 代码如下 import java.util.Arrays;public class ShellSort {public static void main(String[] args) {int[] arr {8,9,1,7,2,3,5,4,6,0};shell(arr);System.out.println(Arrays.toString(arr));}public static void shell(int[] arr) {int size arr.length;for (int gap size 1;gap 1; gap 1) {for (int i gap; i size;i) {int key arr[i];int j i-gap;while(j 0 arr[j] key) {arr[jgap] arr[j];j - gap;}arr[j gap] key;}}}} 6.0 实现归并排序 归并排序Merge Sort是一种经典的分治算法它的基本思想是将待排序的数组递归地分成两个子数组分别对两个子数组进行排序然后将两个已排序的子数组合并成一个有序的数组。归并排序的过程可以描述为“分而治之”。 归并排序是一种稳定的排序算法它的时间复杂度始终为 O(n log n) 这使得它在处理大规模数据时具有较好的性能。然而归并排序的空间复杂度较高因为它需要额外的空间来存储临时数组。 6.1 递归实现归并排序
归并排序的算法步骤如下 1. 分将待排序的数组分成两个子数组直到子数组的长度为1。 2. 治对每个子数组进行递归排序直到子数组有序。 3. 合将两个有序的子数组合并成一个有序的数组。 使用递归实现归并的动态演示过程 代码如下 import javax.print.DocFlavor;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.IllegalFormatCodePointException;public class mergeSort {public static void main(String[] args) {int[] arr {1,10,7,4,8,3,2,6,9,5};int[] a new int[arr.length];//spilt(arr,0, arr.length - 1,a);//merge(arr);spiltInsert(arr,0,arr.length,a);System.out.println(Arrays.toString(arr));}//使用递归实现归并排序public static void spilt(int[] arr,int left,int right, int[] a) {if (left right) {return;}//分int mid (left right) 1;spilt(arr,left,mid,a);spilt(arr,mid1,right,a);//合mergeArr(arr,left,mid,mid 1,right,a);System.arraycopy(a,left,arr,left,right - left 1);}//非递归实现两个有序数组合并public static void mergeArr(int[] arr,int i,int iEnd,int j,int jEnd,int[] a) {int k i;while(i iEnd j jEnd) {if (arr[i] arr[j]) {a[k] arr[i];i;}else {a[k] arr[j];j;}k;}if (i iEnd) {System.arraycopy(arr,j,a,k,jEnd - j 1);}if (j jEnd) {System.arraycopy(arr,i,a,k,iEnd - i 1);}}}6.2 使用非递归实现归并排序 非递归归并排序的关键是正确地计算子数组的大小并进行合并操作直到整个数组都被合并为一个有序序列。
以下是非递归归并排序的主要步骤 1. 从数组中的每个元素开始将其视为一个大小为1的有序序列。 2. 通过迭代将相邻的有序序列合并为更大的有序序列直到整个数组变为一个有序序列。 3. 在每次迭代中合并的子数组大小以指数级增加直到整个数组都被合并为一个有序序列。
代码如下 //使用递归实现归并排序public static void spilt(int[] arr,int left,int right, int[] a) {if (left right) {return;}//分int mid (left right) 1;spilt(arr,left,mid,a);spilt(arr,mid1,right,a);//合mergeArr(arr,left,mid,mid 1,right,a);System.arraycopy(a,left,arr,left,right - left 1);}//非递归实现两个有序数组合并public static void mergeArr(int[] arr,int i,int iEnd,int j,int jEnd,int[] a) {int k i;while(i iEnd j jEnd) {if (arr[i] arr[j]) {a[k] arr[i];i;}else {a[k] arr[j];j;}k;}if (i iEnd) {System.arraycopy(arr,j,a,k,jEnd - j 1);}if (j jEnd) {System.arraycopy(arr,i,a,k,iEnd - i 1);}} 6.3 递归归并排序 插入排序 即集合了递归排序的优点与插入排序的优点实现更加高效排序。
代码如下 //递归归并 插入排序public static void spiltInsert(int[] arr,int left,int right,int[] a) {if (right - left 32) {insert(arr,left,right);return;}int m (left right) 1;spiltInsert(arr,left,m,a);spiltInsert(arr,m1,right,a);mergeArr(arr,left,m,m1,right,a);System.arraycopy(a,left,arr,left,right-left1);}//插入排序public static void insert(int[] arr,int left, int right) {for (int i left 1; i right; i) {int key arr[i];int j i - 1;while (j left arr[j] key) {arr[j1] arr[j];j--;}arr[j1] key;}} 7.0 快速排序 快速排序是一种常用的排序算法它基于分治的思想。快速排序的基本思想是选择一个基准值然后将数组分割成两部分使得左边的元素都小于基准值右边的元素都大于基准值。然后对左右两部分分别进行递归排序直到整个数组有序。
以下是快速排序的主要步骤 1.选择一个基准值通常是数组中的第一个元素。 2.将数组分割成两部分使得左边的元素都小于基准值右边的元素都大于基准值。这一步称为分区操作。 3. 递归地对左右两部分进行快速排序。 4. 当左右两部分都有序时整个数组也就有序了。 7.1 单边循环快排 单边循环快排的时间复杂度为 O(n logn)空间复杂度为 O(logn)。单边循环快排也称为荷兰国旗问题解法是快速排序算法的一种实现方式它通过使用单个指针在数组中进行循环遍历实现数组的分区和排序。
代码如下 //单边循环快排要点://选择最右侧元素作为基准点//j 找比基准点小的i 找基准点大的一旦找到二者进行交换:// 交换时机: j 找到小的且与 i 不相等// i 找到 基准点元素后不应自增// 最后基准点与 i 交换 i 即为基准点最终索引public static void quickSort(int[] arr) {recursion(arr,0,arr.length-1);}private static void recursion(int[] arr,int left,int right) {if (left right) {return;}//先找到基准点int m benchmark(arr,left,right);//切分基准点两侧recursion(arr, left, m - 1);recursion(arr, m 1, right);}private static int benchmark(int[] arr,int left,int right) {int temp arr[right];//i 找最大值、 j 找最小值一旦 j 找到最小值且 j ! i 就可以交换了int i left;int j left;while (j right) {if (arr[j] temp) {if (i ! j) {//交换swap(arr,i,j);}i;}j;}swap(arr,i,right);return i;}private static void swap(int[] arr,int i,int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;} 7.2 双边循环快排 双边循环快排是一种快速排序算法的实现方式它通过不断地将数组分割成两部分并对每一部分进行递归排序来实现排序。与单边循环快排相比双边循环快排在分割数组时使用两个指针分别从数组的两端向中间移动以实现更高效的分割操作。 双边循环快排的时间复杂度为 O(nlogn)空间复杂度为 O(logn)。它是一种高效的排序算法在大多数情况下都能够快速地对数组进行排序。
具体实现过程如下 1. 选择数组中的一个元素作为基准值通常选择第一个元素。 2. 设置两个指针一个指向数组的起始位置另一个指向数组的末尾位置。 3. 从起始位置开始找到第一个大于基准值的元素并将其位置记录下来。 4. 从末尾位置开始找到第一个小于基准值的元素并将其位置记录下来。 5. 交换这两个元素的位置然后继续寻找下一个需要交换的元素直到两个指针相遇。 6. 将基准值与指针相遇的位置的元素交换位置这样基准值左边的元素都小于基准值右边的元素都大于基准值。 7. 对基准值左右两个子数组分别进行递归排序。 代码如下 //双边循环快排要点://选择最左侧元素作为基准点//j 找比基准点小的, i 找比基准点大的一旦找到二者进行交换// i 从左向右// j 从右先左// 最后基准点与 i 交换 i 即为基准点最终索引public static void quickSort1(int[] arr) {recursion1(arr,0,arr.length-1);}private static void recursion1(int[] arr,int left,int right) {if (left right) {return;}int m benchmark1(arr,left,right);recursion1(arr,left,m - 1);recursion1(arr,m 1,right);}private static int benchmark1(int[] arr,int left,int right) {int temp arr[left];int i left;int j right;while (i j) {while (i j temp arr[j]) {j--;}while (i j temp arr[i]) {i;}swap(arr,i,j);}swap(arr,left,i);return i;}private static void swap(int[] arr,int i,int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;} 7.3 快速排序的改良升级 考虑快排时遇到的重复元素过多而进行改良。
代码如下 public static void quickSort1(int[] arr) {recursion1(arr,0,arr.length-1);}private static void recursion1(int[] arr,int left,int right) {if (left right) {return;}int m benchmark2(arr,left,right);recursion1(arr,left,m - 1);recursion1(arr,m 1,right);}//考虑快排时遇到的重复元素过多而进行改良private static int benchmark2(int[] arr,int left,int right) {int temp arr[left];int i left 1;int j right;while(i j) {while(i j arr[i] temp) {i;}while (i j arr[j] temp ) {j--;}if (i j) {swap(arr,i,j);i;j--;}}swap(arr,left,j);return j;}
