山东中讯做网站怎么样,郑州网络优化实力乐云seo,天气预报最新天气预报,网站手机模板的特点1. 冒泡排序
(1) 基本思路 冒泡排序是一种简单的、但效率极低的排序算法#xff0c;基本思路是重复地遍历待排序的序列#xff0c;通过相邻元素的比较和交换#xff0c;将较大#xff08;或较小#xff09;的元素逐步冒泡到右侧#xff08;或左侧#xff0…1. 冒泡排序
(1) 基本思路 冒泡排序是一种简单的、但效率极低的排序算法基本思路是重复地遍历待排序的序列通过相邻元素的比较和交换将较大或较小的元素逐步冒泡到右侧或左侧直到整个序列有序为止。 (2) 升序排序
BUBBLE-SORT(a, len)for i 1 ~ len-2dofor j 1 ~ len-i-2doif a[j] a[j1]doswap(a[j], a[j1]);end ifend forend for(3) 分析时间复杂度
程序执行次数化简后时间复杂度for i 1 ~ len-2 l e n − 2 len-2 len−2 O ( l e n ) O(len) O(len)for j 1 ~ len-i-2 ( l e n − 1 ) ⋅ ( l e n − 2 ) 2 \frac{{(len-1) \cdot (len-2)}}{2} 2(len−1)⋅(len−2) O ( l e n 2 ) O(len^2) O(len2)if a[j] a[j1] ( l e n − 1 ) ⋅ ( l e n − 2 ) 2 \frac{{(len-1) \cdot (len-2)}}{2} 2(len−1)⋅(len−2) O ( l e n 2 ) O(len^2) O(len2)swap(a[j], a[j1]) ( l e n − 1 ) ⋅ ( l e n − 2 ) 2 \frac{{(len-1) \cdot (len-2)}}{2} 2(len−1)⋅(len−2) O ( l e n 2 ) O(len^2) O(len2)BUBBLE-SORT 3 l e n 2 − 9 l e n 10 2 ⋅ ( l e n − 2 ) \frac{{3len^2 - 9len 10}}{2} \cdot (len-2) 23len2−9len10⋅(len−2) O ( l e n 3 ) O(len^3) O(len3)
所以冒泡排序的时间复杂度一般在 O ( n 3 ) O(n^3) O(n3) 上下。即使时间复杂度很高但是冒泡排序还是有很高的地位。它既简单又容易实现。
2. 插入排序
(1) 基本思路 插入排序是一种简单直观的排序算法基本思路是将一个待排序的元素插入到已经排好序的子序列中的适当位置直到整个序列有序为止。 (2) 升序排序
INSERTION-SORT(a, len)for i 1 ~ len-1dokey a[i]j i - 1while j 0 and a[j] keydoa[j1] a[j]j j - 1end whilea[j1] keyend for(3) 分析时间复杂度
程序执行次数化简后时间复杂度for i 1 ~ len-1 l e n − 1 len-1 len−1 O ( l e n ) O(len) O(len)while j 0 and a[j] key ( l e n − 1 ) ⋅ ( l e n − 2 ) 2 \frac{{(len-1) \cdot (len-2)}}{2} 2(len−1)⋅(len−2) O ( l e n 2 ) O(len^2) O(len2)a[j1] a[j] ( l e n − 1 ) ⋅ ( l e n − 2 ) 2 \frac{{(len-1) \cdot (len-2)}}{2} 2(len−1)⋅(len−2) O ( l e n 2 ) O(len^2) O(len2)a[j1] key l e n − 1 len-1 len−1 O ( l e n ) O(len) O(len)INSERTION-SORT 3 l e n 2 − 3 l e n 4 2 \frac{{3len^2 - 3len 4}}{2} 23len2−3len4 O ( l e n 2 ) O(len^2) O(len2)
所以插入排序的时间复杂度一般在 O ( n 2 ) O(n^2) O(n2) 上下。它的时间复杂度比冒泡排序低是一种简单且常用的排序算法。
3. 选择排序
(1) 基本思路 选择排序是一种简单直观的排序算法基本思路是找到待排序序列中的最小或最大元素将它与序列的第一个位置进行交换然后再在剩余的序列中找到最小或最大元素将它与序列的第二个位置进行交换以此类推直到整个序列有序为止。 (2) 升序排序
SELECTION-SORT(a, len)for i 1 ~ len-1dominIndex ifor j i1 ~ lendoif a[j] a[minIndex]dominIndex jend ifend forswap(a[i], a[minIndex])end for(3) 分析时间复杂度
程序执行次数化简后时间复杂度for i 1 ~ len-1 l e n − 1 len-1 len−1 O ( l e n ) O(len) O(len)for j i1 ~ len ( l e n − 1 ) ⋅ l e n 2 \frac{{(len-1) \cdot len}}{2} 2(len−1)⋅len O ( l e n 2 ) O(len^2) O(len2)if a[j] a[minIndex] ( l e n − 1 ) ⋅ l e n 2 \frac{{(len-1) \cdot len}}{2} 2(len−1)⋅len O ( l e n 2 ) O(len^2) O(len2)swap(a[i], a[minIndex]) l e n − 1 len-1 len−1 O ( l e n ) O(len) O(len)SELECTION-SORT 3 l e n 2 − 3 l e n 4 2 \frac{{3len^2 - 3len 4}}{2} 23len2−3len4 O ( l e n 2 ) O(len^2) O(len2)
所以选择排序的时间复杂度一般在 O ( n 2 ) O(n^2) O(n2) 上下。虽然时间复杂度较高但选择排序在某些情况下可以比其他排序算法更高效。
4. 快速排序
(1) 基本思路 快速排序是一种高效的排序算法基本思路是通过一趟排序将待排序序列分割成独立的两个部分其中一部分的所有元素都比另一部分的任意元素小然后再对这两部分继续进行排序直到整个序列有序为止。 (2) 升序排序
QUICK-SORT(a, low, high)if low highdopivotIndex PARTITION(a, low, high)QUICK-SORT(a, low, pivotIndex-1)QUICK-SORT(a, pivotIndex1, high)end ifPARTITION(a, low, high)pivotValue a[high]i low - 1for j low ~ high-1doif a[j] pivotValuedoi i 1swap(a[i], a[j])end ifend forswap(a[i1], a[high])return i 1(3) 分析时间复杂度
程序执行次数化简后时间复杂度if low high log 2 ( l e n ) \log_2(len) log2(len) O ( log ( l e n ) ) O(\log(len)) O(log(len))PARTITION(a, low, high) l e n − 1 len-1 len−1 O ( l e n ) O(len) O(len)QUICK-SORT(a, low, pivotIndex-1) l e n 2 − l e n 2 \frac{{len^2 - len}}{2} 2len2−len O ( l e n 2 ) O(len^2) O(len2)QUICK-SORT(a, pivotIndex1, high) l e n 2 − l e n 2 \frac{{len^2 - len}}{2} 2len2−len O ( l e n 2 ) O(len^2) O(len2)QUICK-SORT 3 l e n 2 − 3 l e n 10 2 \frac{{3len^2 - 3len 10}}{2} 23len2−3len10 O ( l e n 2 ) O(len^2) O(len2)PARTITION l e n − 1 len-1 len−1 O ( l e n ) O(len) O(len)
所以快速排序的时间复杂度一般在 O ( n 2 ) O(n^2) O(n2) 上下但在平均情况下时间复杂度为 O ( n log n ) O(n \log n) O(nlogn)。
5. 归并排序
(1) 基本思路 归并排序是一种高效的排序算法基本思路是将待排序序列分成若干个子序列分别进行排序然后再将已排序的子序列合并成更大的有序序列直到最终只有一个有序序列为止。 (2) 升序排序
MERGE-SORT(a, low, high)if low highdomid (low high) / 2MERGE-SORT(a, low, mid)MERGE-SORT(a, mid1, high)MERGE(a, low, mid, high)end ifMERGE(a, low, mid, high)n1 mid - low 1n2 high - midleft new Array[n1]right new Array[n2]for i 0 ~ n1-1doleft[i] a[low i]end forfor j 0 ~ n2-1doright[j] a[mid 1 j]end fori 0j 0k lowwhile i n1 and j n2doif left[i] right[j]doa[k] left[i]i i 1elsea[k] right[j]j j 1end ifk k 1end whilewhile i n1doa[k] left[i]i i 1k k 1end whilewhile j n2doa[k] right[j]j j 1k k 1end while(3) 分析时间复杂度
程序执行次数化简后时间复杂度if low high log 2 ( l e n ) \log_2(len) log2(len) O ( log ( l e n ) ) O(\log(len)) O(log(len))MERGE-SORT(a, low, mid) l e n ⋅ ( log ( l e n ) − 1 ) 2 \frac{{len \cdot (\log(len) - 1)}}{2} 2len⋅(log(len)−1) O ( l e n log ( l e n ) ) O(len \log(len)) O(lenlog(len))MERGE-SORT(a, mid1, high) l e n ⋅ ( log ( l e n ) − 1 ) 2 \frac{{len \cdot (\log(len) - 1)}}{2} 2len⋅(log(len)−1) O ( l e n log ( l e n ) ) O(len \log(len)) O(lenlog(len))MERGE(a, low, mid, high) l e n − 1 len-1 len−1 O ( l e n ) O(len) O(len)MERGE-SORT 3 l e n ⋅ ( log ( l e n ) − 1 ) 2 \frac{{3len \cdot (\log(len) - 1)}}{2} 23len⋅(log(len)−1) O ( l e n log ( l e n ) ) O(len \log(len)) O(lenlog(len))MERGE l e n − 1 len-1 len−1 O ( l e n ) O(len) O(len)
所以归并排序的时间复杂度一般为 O ( n log n ) O(n \log n) O(nlogn)在任何情况下都具有稳定的性能。
