一、減治法在排序算法中的應(yīng)用

插入排序：時間復(fù)雜度O(n^2)，雖然和選擇、冒泡在最壞的情況下時間復(fù)雜度相同，但是插排平均性能在比自身的最差性能快一倍，所以相比選擇、冒泡來說，插排要領(lǐng)先于二者。

public class Main {public static void main(String[] args) {int[] a = {89, 45, 68, 90, 29, 34, 17};for (int i = 1; i < a.length; i++) {int v = a[i];int j = i-1;/*** 在前i-1個有序元素中找到一個合適位置，將a[i]插入* */while (j >= 0 && a[j] > v) {a[j+1] = a[j];j -= 1;}a[j+1] = v;}for (int i = 0; i < a.length; i++) {System.out.print(a[i] + " ");}} } 發(fā)現(xiàn)問題：對于有序數(shù)組這樣的最優(yōu)輸入來說，快排的性能非常好，但是這種情況畢竟沒有太大的實際意義。而當(dāng)大數(shù)據(jù)量測試的時候，快排總是不盡如人意。

優(yōu)化思路：基于快排的一種拓展算法----Shell（希爾）排序

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的减治法在排序算法中的应用（JAVA）--插入排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。