用自己的电脑做视频网站吗,上海中风险地区,青岛网站制作推广,互联网活动策划方案目录 QUESTION:八大排序:Java实现八大排序及算法复杂度分析
ANSWER:
一#xff1a;冒泡排序
1.算法分析
2.时间复杂度分析
3.代码
二#xff1a;选择排序
1.算法分析
2.时间复杂度分析
3.代码
三#xff1a;插入排序
1.算法分析
2.时间复杂度分析
3.代码
四冒泡排序
1.算法分析
2.时间复杂度分析
3.代码
二选择排序
1.算法分析
2.时间复杂度分析
3.代码
三插入排序
1.算法分析
2.时间复杂度分析
3.代码
四归并排序
1.算法分析
2.时间复杂度分析
3.代码
五堆排序
1.算法分析
2.时间复杂度分析
3.代码
六快速排序
1.算法分析
2.时间复杂度分析
3.代码 QUESTION:八大排序:Java实现八大排序及算法复杂度分析
ANSWER:
一冒泡排序
1.算法分析
冒泡排序是对于一个数组从第一个数开始与下一个数进行比较大的冒后面小的冒前面相邻元素依次比较完成一次循环继续下一次循环直至数组有序。
图示 2.时间复杂度分析
由于冒泡排序是两层for循环所以TO(n^2)。
3.代码
*** 冒泡排序*/
public class BubbleSort {public static void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}/*** 比较相邻元素大小每次缩减一* param arr*/public static void bubbleSort(int []arr){if (arrnull){return;}for (int i arr.length-1; i 0 ; i--) {for (int j 0; j i ; j) {if (arr[j]arr[j1]){swap(arr,j,j1);}}}}
}二选择排序
1.算法分析
选择排序是选择数组第一个元素假设为最小元素与后面的所以元素比较比其它元素大就交换位置完成一次循环就从第二个元素开始依次上述过程比较直至数组有序。
图示 2.时间复杂度分析n^
由于选择排序两层for循环所以TO(n^2)。
3.代码
/*** 选择排序*/
public class SelectionSort {public static void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}/*** 假设第一个值为最小元素每次循环与后一个元素比较找到最小元素* param arr*/public static void selectionSort(int []arr){if (arrnull){return;}for (int i 0; i arr.length-1 ; i) {int mini;for (int j i1; j arr.length ; j) {minarr[j]arr[min]?j:min;}swap(arr,i,min);}}
}三插入排序
1.算法分析
插入排序是从数组第二个元素开始找前面的数比较大小如果前面的数大就交换位置然后继续向前比较。每次从第几个元素开始遍历时都把较小的元素插入到该元素前面使其前面数组有序完成一次循环继续循环下一个元素直至数组有序。
图示 2.时间复杂度分析
由于插入排序两层for循环TO(n^2)。
3.代码
public class InsertionSort {public static void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}public static void insertionSort(int []arr){if (arrnull){return;}for (int i 1; i arr.length ; i) {for (int j i-1; j0arr[j]arr[j1]; j--) {swap(arr,j,j1);}}}
}四归并排序
1.算法分析
归并排序是利用二分的思想不断的将数组进行分割为两部分依次比较每部分的最小元素将最小的元素放入辅助数组直到所有元素都插入数组完成排序。
图示 2.时间复杂度分析
由于归并排序是合并的思想所有TO(n*logn)。
3.代码 public class MergeSort {/*** 将数组分段排序插入然后归并排序* param arr* param l* param m* param r*/public static void merge(int []arr,int l,int m,int r){int []helpnew int[r-l1];int i0;int p1l;int p2m1;while (p1mp2r){help[i]arr[p1]arr[p2]?arr[p1]:arr[p2];}while (p1m){help[i]arr[p1];}while (p2r){help[i]arr[p2];}for (int j 0; j help.length ; j) {arr[jl]help[j];}}/*** 递归进行分段归并* param arr* param l* param r*/public static void mergeSort(int []arr,int l,int r){if (lr){return;}int mid((r-l)1)l;mergeSort(arr,l,mid);mergeSort(arr,mid1,r);merge(arr,l,mid,r);}/*** 数组归并排序*/public static void mergeSort(int []arr){if (arrnull){return;}mergeSort(arr,0,arr.length-1);}
}五堆排序
1.算法分析
堆排序的思想是根据二叉树的大根堆和小根堆的概念形成首先依照数组建立大根堆之后为了防止某一个元素的变化而引起整个大根堆的变化建立一个修改二叉树为大根堆的方法该数组保持大根堆的排序。之后交换大根堆元素得到有序数组。
图示 2.时间复杂度分析
堆排序建立大根堆的过程TO(n*logn)。
3.代码
/*** 堆排序大根堆小根堆*/
public class HeapSort{/*** 建立大根堆当孩子结点大于根结点进行交换没有进行左右孩子结点的比较* param arr* param index*/public static void heapInsert(int []arr,int index){while(arr[index]arr[(index-1)/2]){swap(arr,index,(index-1)/2);index(index-1)/2;}}/*** 修改数组为大根堆* param arr* param index* param size*/public static void heapModifiy(int []arr,int index,int size){int left2*index1;while(leftsize){//兄弟之间结点排序int largestarr[left1]arr[left](left1)size?left1:left;//孩子结点与根结点进行比较largestarr[index]arr[largest]?index:largest;if (largestindex) {break;}swap(arr,index,largest);indexlargest;left2*index1;}}/*** 堆排序* param arr*/public static void heapSort(int []arr){if (arrnull||arr.length0) {return;}for (int i0;iarr.length ;i ) {heapInsert(arr,i);}int sizearr.length;swap(arr,0,--size);while(size0){heapModifiy(arr,0,size);swap(arr,0,--size);}}public static void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}
} 六快速排序
1.算法分析
快速排序的基本思想是有荷兰国旗问题的相似先是随机产生一个范围进行数组的划分小于区域在左边等于区域在中间等于区域在右边直至数组完成排序。
图示 2.时间复杂度分析
快速排序TO(n*logn)。
3.代码
/*** 快速排序*/
public class QuickSort {/***给定范围划分大于区域等于区域小于区域排序* param arr* param l* param r* return*/public static int[] partition(int[] arr, int l, int r) {int less l - 1;int more r;while (l more) {if (arr[l] arr[r]) {swap(arr,less,l);}else if (arr[l]arr[r]){l;}else{swap(arr,--more,l);}}swap(arr,more,r);return new int[]{less1,more};}/*** 产生一个随机范围进行划分排序* param arr* param l* param r*/public static void quickSort(int []arr,int l,int r){if (lr){swap(arr, l(int) (Math.random()*(r-l1)),r);int []partitionpartition(arr,l,r);quickSort(arr,l,partition[0]-1);quickSort(arr,partition[1]1,r);}}/*** 快速排序* param arr*/public static void quickSort(int []arr){if (arrnull){return;}quickSort(arr,0,arr.length-1);}public static void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}
}
