ftp怎么上传网站,建设法规的网站,南京品牌网站设计,建网站需要几程序员目录
1.Java冒泡排序#xff08;Bubble Sort#xff09;
1.冒泡排序
2.冒泡排序的算法原理
3.冒泡排序的复杂度和性能
4.形成代码
2.Java快速排序#xff08;Quick Sort#xff09;
3.Java归并排序#xff08;Merge Sort#xff09;
4.Java选择排序#xff08;S…目录
1.Java冒泡排序Bubble Sort
1.冒泡排序
2.冒泡排序的算法原理
3.冒泡排序的复杂度和性能
4.形成代码
2.Java快速排序Quick Sort
3.Java归并排序Merge Sort
4.Java选择排序Selection Sort
5.Java直接插入排序
6.Java希尔排序Shell Sort 1.Java冒泡排序Bubble Sort
1.冒泡排序
冒泡排序Bubble Sort是编程中较简单的一种排序算法。它重复地走访要排序的数列一次比较两个元素如果它们的顺序错误就把它们交换过来。重复地进行走访数列的工作直到没有再需要交换的元素这也就意味着该数列已经完成排序。
冒泡排序就像气泡从水中出现一样在气泡排序中最小或最大的数字取决于我们是按升序还是降序排序数组气泡朝着数组的开始或结束冒出。
2.冒泡排序的算法原理
1比较相邻的元素如果第一个比第二个大就交换他们两个。
2对每一对相邻元素做同样的工作从开始第一对到结尾的最后一对在这一点最后的元素应该会是最大的数。
3针对所有的元素重复以上的步骤除了最后一个。
4持续对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。
3.冒泡排序的复杂度和性能
与其他排序算法诸如快速排序、归并排序或shell排序相比冒泡排序表现不佳。这些算法的平均情况复杂度为O(nlogn)而冒泡排序平均情况复杂度为O(n^2)。
在最佳情况下冒泡排序比具有O(n)性能的快速排序更好。冒泡排序比快速排序或归并排序慢三倍即使n100但它更容易实现和记忆。
冒泡排序的复杂度和性能如下
1冒泡排序最差情况性能O(n^2)
2冒泡排序最佳情况性能O(n)
3冒泡排序平均情况性能O(n^2)
4.形成代码
//冒泡排序
public static void bubbleSort(int[] arr) {//外层循环用来控制数组循环的圈数for(int i0;iarr.length-1;i) {//内层循环用来完成元素值比较把大的元素值互换到后面for(int j0;jarr.length-1-i;j) {if(arr[j] arr[j1]) {int temp arr[j];arr[j] arr[j1];arr[j1] temp;}}}//输出结果for(int n:nums) {System.out.println(n);}
}
例如
public class Main {public static void main(String[] args) {int a[] {6,1,15,32,9};for(int i1;ia.length;i) {for(int j0;ja.length-1;j) {if(a[j] a[j1]) {int temp a[j];a[j] a[j1];a[j1] temp;}}}System.out.println(冒泡排序的结果是);for(int temp:a) {System.out.print(temp );}}
}
运行结果如下
冒泡排序的结果是
1 6 9 15 32
2.Java快速排序Quick Sort
快速排序Quick Sort是基于二分思想对冒泡排序的一种改进。主要思想是确立一个基数将小于基数的数字放到基数的左边大于基数的数字放到基数的右边然后再对这两部分数字进一步排序从而实现对数组的排序。
其优点是效率高时间复杂度平均为O(nlogn)顾名思义快速排序是最快的排序算法耗费的资源少最佳情况下空间复杂度为O(logn)每一次都平分数组的情况代码较为简单。
其缺点是不稳定初始序列有序或基本有序时时间复杂度降为O(n^2)。
例如
public class Main {//快排实现方法public static void quickRow(int[] array,int low,int high) {int i,j,pivot;//结束条件if(low high) {return;}i low;j high;//选择的节点这里选择的数组的第一数作为节点pivot array[low];while(ij) {//从右往左找比节点小的数循环结束要么找到了要么ijwhile(array[j] pivot ij) {j--;}//从左往右找比节点大的数循环结束要么找到了要么ijwhile(array[i] pivot ij) {i;}//如果i!j说明都找到了就交换这两个数if(ij) {int temp array[i];array[i] array[j];array[j] temp;}}//ij一轮循环结束交换节点的数和相遇点的数array[low] array[i];array[i] pivot;//数组“分两半”,再重复上面的操作quickRow(array,low,i-1);quickRow(array,i1,high);}public static void main(String[] args) {int[] array {6,17,38,59,2,10};int low 0,high array.length-1;quickRow(array,low,high);for (int i : array){System.out.println(i);}}
}
运行结果如下
2
6
10
17
38
59
3.Java归并排序Merge Sort
归并排序Merge Sort是建立在归并操作上的一种有效的稳定的排序算法该算法是采用分治法Divide and Conquer的一个非常典型的应用。
归并排序将两个有序的子序列合并得到一个完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序的列表合并成一个有序的列表我们称之为二路归并。
归并排序的速度仅次于快速排序时间复杂度为O(nlogn)。其拆分过程中使用了二分思想是一个递归的过程为了减少在递归过程中不断开辟空间的问题我们可以在归并排序之前先开辟出一个临时空间在递归过程中统一使用此空间进行归并即可。
例如
import java.util.Arrays;
public class Main {public static void main(String[] args) {int[] arr new int[]{86,23,7,45,19,10};int left 0;int right arr.length-1;int[] tem Arrays.copyOf(arr,arr.length);print(arr);mergeSort(arr,left,right,tem);print(arr);}public static void mergeSort(int[] arr,int left,int right,int[] tem) {if(right-left1) {return;}int mid left (right-left)/2;mergeSort(arr,left,mid,tem);mergeSort(arr,mid1,right,tem);merge(arr,left,mid,right,tem);}private static void merge(int[] arr,int left,int mid,int right,int[] tem) {int index 0;int l left,r mid1;while(l mid r right) {if(arr[l]arr[r]) {tem[index] arr[l];}else{tem[index] arr[r];}}while(l mid) {tem[index] arr[l];}while(r right) {tem[index] arr[r];}for(int i0;i(right-left1);i) {arr[lefti] tem[i];}}private static void print(int[] arr) {for (int i : arr) {System.out.print(i\t);}System.out.println();}
}
运行结果如下
86 23 7 45 19 10
7 10 19 23 45 86
4.Java选择排序Selection Sort
选择排序Selection Sort是一种简单直观的排序算法其算法原理为首先在未排序的序列中找到最小大的元素存放到排序序列的起始位置然后再从剩余未排序的元素中继续寻找最小大的元素存放到已排序序列的末尾以此类推直到所有元素均排序完成。
选择排序一共有“数组数-1”轮排序每一轮排序又是一个循环循环的规则如下
1先假定当前这轮循环的第一个数是最小数。
2然后和后面每个数进行比较如果发现有比当前数更小的数则重新确定最小数并得到下标。
3当遍历到数组的最后时就得到本轮最小的数。
4和当前循环的第一个数进行交换。
例如
import java.util.Arrays;
public class Main {public static void main(String[] args) {int[] arr new int[]{19,26,8,35,41,77};for(int i0;iarr.length-1;i) { //每次循环都会找出最小的数int minIndex i; //记录最小数的下标int minNum arr[i]; //记录最小数for(int ji1;jarr.length;j) { //每次循环都会找出最小的数if(arr[j]minNum) { //如果当前数比最小数小则更新最小数minNum arr[j]; //更新最小数minIndex j; //更新最小数的下标}}arr[minIndex] arr[i]; //将最小数放到最前面arr[i] minNum; //将标志位放到最小数原来所在的位置}for(int i0;iarr.length;i) {System.out.println(arr[i]);}}
}
运行结果如下
8
19
26
35
41
77
5.Java直接插入排序
直接插入排序是指将一个个待排序的元素插入到前面已经排好序的有序序列中去直到插完所有元素为止主要步骤如下
1先假设第一个元素已经排好序。
2然后依次取出还需要进行排序的下一个元素也就是排序完成的元素后面的下一个元素取出下一个元素设为待插入元素在已经排序的元素序列中从后向前扫描如果该元素已排序大于待插入元素将该元素移到下一位置。
3重复步骤2直到找到已排序的元素小于或者等于待排序元素的位置插入元素。
4重复步骤2、步骤3完成排序。
例如
import java.util.Arrays;
public class Main {public static void main(String args[]) {int[] arr new int[]{17,62,39,52,8,24};for(int i1;iarr.length;i) { //从第二个元素开始比较int temp arr[i]; //记录当前元素for(int ji-1;j0;j--) { //从最后一个元素开始比较if(arr[j]temp) { //如果比当前元素大arr[j1] arr[j]; //从该处往后所有元素向后移动一位arr[j] temp; //将当前元素插入到arr[j]中}}}for(int i0;iarr.length;i) {System.out.print(arr[i] );}}
}
运行结果如下
8 17 24 39 52 62
6.Java希尔排序Shell Sort
希尔排序Shell Sort是插入排序的一种也是直接插入排序的更高效的改进版本希尔排序充分利用了插入排序的两个特点
1当数据规模小的时候非常高效。
2当给定数据已经有序时的时间复杂度为O(n)。
所以Shell排序每次把数据分成若干块来使用插入排序而且之后在这若干个小块排好序的情况下把它们合成大一点的小块继续使用插入排序不停地合并小块直到最后一个小块。
这里每次分成若干个小块是通过“增量”来控制的开始的时候增量较大接近n/2从而使得分割出来接近n/2个小块逐渐的减小“增量”最终减小到1。
例如
public class Main {public static int count 0;public static void shellSort(int[] data) {// 计算出最大的h值int h 1;while(h data.length / 3) {h h * 3 1;}while(h 0) {for(int ih;idata.length;ih) {if(data[i] data[i-h]) {int tmp data[i];int j i-h;while(j 0 data[j] tmp) {data[jh] data[j];j - h;}data[jh] tmp;print(data);}}// 计算出下一个h值h (h - 1) / 3;}}public static void print(int[] data) {for(int i0;i data.length;i) {System.out.print(data[i]\t);}System.out.println();}public static void main(String[] args) {int[] data new int[]{4,6,1,9,5,8};print(data);shellSort(data);print(data);}
}
运行结果如下
4 6 1 9 5 8
1 4 6 9 5 8
1 4 5 6 9 8
1 4 5 6 8 9
1 4 5 6 8 9
