欧美日一区二区|初爱ねんね播放|翘臀美深夜福利视频|欧美一区二区日韩一区二区|女人到达高清视频播放大全|国产精品麻豆精品A片|国产99视频精品免视看7

  1. 首頁(yè) > 生活 > >

十大排序算法python 十大排序算法

生活百科十大排序算法

冒泡排序

  1. 從數(shù)組頭開(kāi)始，比較相鄰的元素 。如果第一個(gè)比第二個(gè)大(小)，就交換它們兩個(gè)
  2. 對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到尾部的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大(小)的數(shù)
  3. 重復(fù)步驟1~2，重復(fù)次數(shù)等于數(shù)組的長(zhǎng)度，直到排序完成

十大排序算法python 十大排序算法

文章插圖
代碼實(shí)現(xiàn)對(duì)下面數(shù)組實(shí)現(xiàn)排序：{24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9}
代碼實(shí)現(xiàn)
public class BubbleSort {public static final int[] ARRAY = {24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9};public static void main(String[] args) {print(ARRAY);System.out.println("============================================");print(sort(ARRAY));}public static int[] sort(int[] array) {if (array.length == 0) {return array;}for (int i = 0; i < array.length; i++) {//array.length - 1 -i 已經(jīng)冒泡到合適位置無(wú)需在進(jìn)行排序，減少比較次數(shù)for (int j = 0; j < array.length - 1 -i; j++) {//前面的數(shù)大于后面的數(shù)交換if (array[j + 1] < array[j]) {int temp = array[j + 1];array[j + 1] = array[j];array[j] = temp;}}}return array;}public static void print(int[] array) {for (int i : array) {System.out.print(i + "");}System.out.println("");}}時(shí)間復(fù)雜度對(duì)于上面12個(gè)數(shù)據(jù)項(xiàng)，從第一個(gè)元素開(kāi)始，第一趟比較了11次，第二趟比較了10次，依次類推，一直到最后一趟，就是：
11 + 10 + 9 + 8 + 7 + 6 + 5+ 4 + 3+ 2 + 1=66次若有n個(gè)元素，則第一趟比較為(n-1)次，第二趟比較為(n-2)次，依次類推：
(n-1) + (n-2) + (n-3) + ...+ 2 + 1 = n * (n-1)/2在大O表示法中，去掉常數(shù)系數(shù)和低階項(xiàng)，該排序方式的時(shí)間復(fù)雜度為：O(n2)
算法穩(wěn)定性假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的 。——百度百科
在代碼中可以看到，array[j + 1] = array[j]的時(shí)候，我們可以不移動(dòng)array[i]和array[j]，所以冒泡排序是穩(wěn)定的 。
選擇排序
  1. 找到數(shù)組中最大（或最小）的元素
  2. 將它和數(shù)組的第一個(gè)元素交換位置（如果第一個(gè)元素就是最大（小）元素那么它就和自己交換）
  3. 在剩下的元素中找到最大（小）的元素，將它與數(shù)組的第二個(gè)元素交換位置 。如此往復(fù)，直到將整個(gè)數(shù)組排序 。

十大排序算法python 十大排序算法

文章插圖
代碼實(shí)現(xiàn)對(duì)下面數(shù)組實(shí)現(xiàn)排序：{87, 23, 7, 43, 78, 62, 98, 81, 18, 53, 73, 9}
動(dòng)圖演示
十大排序算法python 十大排序算法

文章插圖
代碼實(shí)現(xiàn)
public class SelectionSort {public static final int[] ARRAY = {87, 23, 7, 43, 78, 62, 98, 81, 18, 53, 73, 9};public static int[] sort(int[] array) {if (array.length == 0) {return array;}for (int i = 0; i < array.length; i++) {//最小數(shù)的下標(biāo)，每個(gè)循環(huán)開(kāi)始總是假設(shè)第一個(gè)數(shù)最小int minIndex = i;for (int j = i; j < array.length; j++) {//找到最小索引if (array[j] < array[minIndex]) {//保存最小索引minIndex = j;}}//最小索引的值int temp = array[minIndex];array[minIndex] = array[i];array[i] = temp;}return array;}public static void print(int[] array) {for (int i : array) {System.out.print(i + "");}System.out.println("");}public static void main(String[] args) {print(ARRAY);System.out.println("============================================");print(sort(ARRAY));}}時(shí)間復(fù)雜度很明顯，和冒泡排序相比，在查找最小（或最大）元素的索引，比較次數(shù)仍然保持為O(n2)
，但元素交換次數(shù)為O(n) 。
算法穩(wěn)定性選擇排序是給每個(gè)位置選擇當(dāng)前元素最小的，比如給第一個(gè)位置選擇最小的，在剩余元素里面給第二個(gè)元素選擇第二小的，依次類推，直到第n-1個(gè)元素，第n個(gè)元素不用選擇了，因?yàn)橹皇Ｏ滤粋€(gè)最大的元素了 。那么，在一趟選擇，如果一個(gè)元素比當(dāng)前元素小，而該小的元素又出現(xiàn)在一個(gè)和當(dāng)前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了 。舉個(gè)例子，數(shù)組5，8，5，2，9，我們知道第一遍選擇第1個(gè)元素5會(huì)和2交換，那么原序列中兩個(gè)5的相對(duì)前后順序就被破壞了，所以選擇排序是一個(gè)不穩(wěn)定的排序算法 。