欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

    1. Java實(shí)現(xiàn)插入排序,希爾排序和歸并排序

       更新時(shí)間:2022年12月22日 11:05:37   作者:程序小猿2  
      這篇文章主要為大家詳細(xì)介紹了插入排序,希爾排序和歸并排序的多種語(yǔ)言的實(shí)現(xiàn)(JavaScript、Python、Go語(yǔ)言、Java),感興趣的小伙伴可以了解一下

      插入排序

      插入排序的代碼實(shí)現(xiàn)雖然沒(méi)有冒泡排序和選擇排序那么簡(jiǎn)單粗暴,但它的原理應(yīng)該是最容易理解的了,因?yàn)橹灰蜻^(guò)撲克牌的人都應(yīng)該能夠秒懂。插入排序是一種最簡(jiǎn)單直觀的排序算法,它的工作原理是通過(guò)構(gòu)建有序序列,對(duì)于未排序數(shù)據(jù),在已排序序列中從后向前掃描,找到相應(yīng)位置并插入。

      插入排序和冒泡排序一樣,也有一種優(yōu)化算法,叫做拆半插入。

      算法步驟

      1.將第一待排序序列第一個(gè)元素看做一個(gè)有序序列,把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列。

      2.從頭到尾依次掃描未排序序列,將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。(如果待插入的元素與有序序列中的某個(gè)元素相等,則將待插入元素插入到相等元素的后面。)

      動(dòng)圖演示

      JavaScript代碼實(shí)現(xiàn)

      function insertionsort(arr){
          var len = arr.length;
          var preIndex,current;
          for(var i = 1;i < len;i++){
              preIndex = i - 1;
              current = arr[i];
              while(preIndex >= 0 && arr[preIndex] > current){
                  arr[preIndex+1] = arr[preIndex];
                  preIndex--;
              }
              arr[preIndex+1] = current;
          }
          return arr;
      }    

      Python代碼實(shí)現(xiàn)

      def insertionSort(arr):
          for i in range(len(arr)):
              preIndex = i-1
              current = arr[i]
              while preIndex >= 0 and arr[preIndex] > current:
                  arr[preIndex+1] = arr[preIndex]
                  preIndex-=1
              arr[preIndex+1] = current
          return arr
      

      Go代碼實(shí)現(xiàn)

      func insertionSort(arr []int)[]int{
          for i := range arr {
              preIndex := i - 1
              current := arr[i]
              for preIndex >= 0 && arr[preIndex] > current {
                  arr[preIndex+1] = arr[preIndex]
                  preIndex -= 1
              }
              arr[preIndex+1] = current
          }
          return arr
      }

      Java代碼實(shí)現(xiàn)

      public class InsertSort implements IArraySort {
      
          @Override
          public int[] sort(int[] sourceArray) throws Exception {
              //對(duì)arr進(jìn)行拷貝,不改變參數(shù)內(nèi)容
              int[] arr = Array.copyOf(sourceArray,sourceArray.length);
              
              //從下標(biāo)為1的元素開(kāi)始選擇合適的位置插入,因?yàn)橄聵?biāo)為0的只有一個(gè)元素,默認(rèn)是有序的
              for(int i = 1;i < arr.length;i++{
              
                  //記錄要插入的數(shù)據(jù)
                  int temp = arr[i];
                  
                  //從已經(jīng)排序的序列最右邊開(kāi)始比較,找到比其小的數(shù)
                  int j = i;
                  while(j > 0 && temp < arr[j - 1] {
                      arr[j] = arr[j-1];
                      j--;
                  }
                  
                  //存在比其小的數(shù),插入
                  if(j != i){
                      arr[j] = temp;
                  }
                  
              }
              return arr;
          }
      }    

      希爾排序

      希爾排序,也稱遞減增量排序算法,是插入排序的一種更高效的改進(jìn)版本。但希爾排序是非穩(wěn)定排序算法。

      希爾排序是基于插入排序以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的:

      • 插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí),效率高,即可以達(dá)到線性排序的效率;
      • 但插入排序一般來(lái)說(shuō)是低效的,因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位;

      希爾排序的基本思想是:先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序,待整個(gè)序列中的記錄“基本有序”時(shí),再對(duì)全體記錄進(jìn)行依次直接插入排序。

      算法步驟

      • 選擇一個(gè)增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1;
      • 按增量序列個(gè)數(shù) k,對(duì)序列進(jìn)行 k 趟排序;
      • 每趟排序,根據(jù)對(duì)應(yīng)的增量 ti,將待排序列分割成若干長(zhǎng)度為 m 的子序列,分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為 1 時(shí),整個(gè)序列作為一個(gè)表來(lái)處理,表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。

      JavaScript代碼實(shí)現(xiàn)

      function shellSort(arr) {
          var len = arr.length,
              temp,
              gap = 1;
          while(gap < len/3) { //動(dòng)態(tài)定義間隔序列
              gap =gap*3+1;
          }
          for (gap; gap > 0; gap = Math.floor(gap/3)) {
              for (var i = gap; i < len; i++) {
                  temp = arr[i];
                  for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                      arr[j+gap] = arr[j];
                  }
                  arr[j+gap] = temp;
              }
          }
          return arr;
      }

      python代碼實(shí)現(xiàn)

      def shellSort(arr):
          import math
          gap=1
          while(gap < len(arr)/3):
              gap = gap*3+1
          while gap > 0:
              for i in range(gap,len(arr)):
                  temp = arr[i]
                  j = i-gap
                  while j >=0 and arr[j] > temp:
                      arr[j+gap]=arr[j]
                      j-=gap
                  arr[j+gap] = temp
              gap = math.floor(gap/3)
          return arr
      }

      Go代碼實(shí)現(xiàn)

      func shellSort(arr []int) []int {
          length := len(arr)
          gap := 1
          for gap < gap/3 {
              gap = gap*3 + 1
          }
          for gap > 0 {
              for i := gap; i < length; i++ {
                  temp := arr[i]
                  j := i - gap
                  for j >= 0 && arr[j] > temp {
                      arr[j+gap] = arr[j]
                      j -= gap
                  }
                  arr[j+gap] = temp
              }
              gap = gap / 3
          }
          return arr
      }

      Java代碼實(shí)現(xiàn)

      public class ShellSort implements IArraySort{
      
          @Override
          public int[] sort(int[] sourceArray) throws Exception{
              //對(duì)arr進(jìn)行拷貝,不改變參數(shù)內(nèi)容
              int[] arr = Arrays.copyOf(sourceArray,sourceArray.length);
              
              int gap = 1;
              while(gap < arr.length/3){
                  gap = gap * 3 = 1;
              }
              
              while(gap > 0){
                  for (int i = gap; i < arr.length; i++) {
                      int tmp = arr[i];
                      int j = i - gap;
                      while (j >= 0 && arr[j] > tmp) {
                          arr[j + gap] = arr[j];
                          j -= gap;
                      }
                      arr[j + gap] = tmp;
                  }
                  gap = (int) Math.floor(gap / 3);
              }
      
              return arr;
          }
      }

      歸并排序

      歸并排序(Merge sort)是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個(gè)非常典型的應(yīng)用。

      作為一種典型的分而治之思想的算法應(yīng)用,歸并排序的實(shí)現(xiàn)由兩種方法:

      • 自上而下的遞歸(所有遞歸的方法都可以用迭代重寫(xiě),所以就有了第 2 種方法);
      • 自下而上的迭代;

      在《數(shù)據(jù)結(jié)構(gòu)與算法 JavaScript 描述》中,作者給出了自下而上的迭代方法。但是對(duì)于遞歸法,作者卻認(rèn)為:

      However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

      然而,在 JavaScript 中這種方式不太可行,因?yàn)檫@個(gè)算法的遞歸深度對(duì)它來(lái)講太深了。

      說(shuō)實(shí)話,我不太理解這句話。意思是 JavaScript 編譯器內(nèi)存太小,遞歸太深容易造成內(nèi)存溢出嗎?還望有大神能夠指教。

      和選擇排序一樣,歸并排序的性能不受輸入數(shù)據(jù)的影響,但表現(xiàn)比選擇排序好的多,因?yàn)槭冀K都是 O(nlogn) 的時(shí)間復(fù)雜度。代價(jià)是需要額外的內(nèi)存空間。

      算法步驟

      1.申請(qǐng)空間,使其大小為兩個(gè)已經(jīng)排序序列之和,該空間用來(lái)存放合并后的序列;

      2.設(shè)定兩個(gè)指針,最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置;

      3.比較兩個(gè)指針?biāo)赶虻脑?,選擇相對(duì)小的元素放入到合并空間,并移動(dòng)指針到下一位置;

      4.重復(fù)步驟 3 直到某一指針達(dá)到序列尾;

      5.將另一序列剩下的所有元素直接復(fù)制到合并序列尾。

      動(dòng)圖演示

      JavaScript代碼實(shí)現(xiàn)

      function mergeSort(arr) { // 采用自上而下的遞歸方法
          var len = arr.length;
          if(len < 2) {
              return arr;
          }
          var middle = Math.floor(len / 2),
              left = arr.slice(0, middle),
              right = arr.slice(middle);
          return merge(mergeSort(left), mergeSort(right));
      }
      
      function merge(left, right)
      {
          var result = [];
      
          while (left.length && right.length) {
              if (left[0] <= right[0]) {
                  result.push(left.shift());
              } else {
                  result.push(right.shift());
              }
          }
      
          while (left.length)
              result.push(left.shift());
      
          while (right.length)
              result.push(right.shift());
      
          return result;
      }

      python代碼實(shí)現(xiàn)

      def mergeSort(arr):
          import math
          if(len(arr)<2):
              return arr
          middle = math.floor(len(arr)/2)
          left, right = arr[0:middle], arr[middle:]
          return merge(mergeSort(left), mergeSort(right))
          
      def merge(left,right):
          result = []
          while left and right:
              if left[0] <= right[0]:
                  result.append(left.pop(0));
              else:
                  result.append(right.pop(0));
          while left:
              result.append(left.pop(0));
          while right:
              result.append(right.pop(0));
          return result
      

      Go代碼實(shí)現(xiàn)

      func mergeSort(arr []int) []int {
          length := len(arr)
          if length < 2 {
              return arr
          }
          middle := length / 2
          left := arr[0:middle]
          right := arr[middle:]
          return merge(mergeSort(left), mergeSort(right))
      }
      
      func merge(left []int, right []int) []int {
          var result []int
          for len(left) != 0 && len(right) != 0 {
              if left[0] <= right[0] {
                  result = append(result, left[0])
                  left = left[1:]
              } else {
                  result = append(result, right[0])
                  right = right[1:]
              }
          }
      
          for len(left) != 0 {
              result = append(result, left[0])
              left = left[1:]
          }
      
          for len(right) != 0 {
              result = append(result, right[0])
              right = right[1:]
          }
      
          return result
      }

      Java代碼實(shí)現(xiàn)

      public class MergeSort implements IArraySort {
      
          @Override
          public int[] sort(int[] sourceArray) throws Exception {
              // 對(duì) arr 進(jìn)行拷貝,不改變參數(shù)內(nèi)容
              int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
      
              if (arr.length < 2) {
                  return arr;
              }
              int middle = (int) Math.floor(arr.length / 2);
      
              int[] left = Arrays.copyOfRange(arr, 0, middle);
              int[] right = Arrays.copyOfRange(arr, middle, arr.length);
      
              return merge(sort(left), sort(right));
          }
      
          protected int[] merge(int[] left, int[] right) {
              int[] result = new int[left.length + right.length];
              int i = 0;
              while (left.length > 0 && right.length > 0) {
                  if (left[0] <= right[0]) {
                      result[i++] = left[0];
                      left = Arrays.copyOfRange(left, 1, left.length);
                  } else {
                      result[i++] = right[0];
                      right = Arrays.copyOfRange(right, 1, right.length);
                  }
              }
      
              while (left.length > 0) {
                  result[i++] = left[0];
                  left = Arrays.copyOfRange(left, 1, left.length);
              }
      
              while (right.length > 0) {
                  result[i++] = right[0];
                  right = Arrays.copyOfRange(right, 1, right.length);
              }
      
              return result;
          }
      
      }

      以上就是Java實(shí)現(xiàn)插入排序,希爾排序和歸并排序的詳細(xì)內(nèi)容,更多關(guān)于Java排序的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

      相關(guān)文章

      • idea在運(yùn)行期間,實(shí)現(xiàn)讓修改的頁(yè)面實(shí)時(shí)生效

        idea在運(yùn)行期間,實(shí)現(xiàn)讓修改的頁(yè)面實(shí)時(shí)生效

        這篇文章主要介紹了idea在運(yùn)行期間,實(shí)現(xiàn)讓修改的頁(yè)面實(shí)時(shí)生效問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
        2024-01-01
      • Java Mybatis框架增刪查改與核心配置詳解流程與用法

        Java Mybatis框架增刪查改與核心配置詳解流程與用法

        MyBatis 是一款優(yōu)秀的持久層框架,它支持自定義 SQL、存儲(chǔ)過(guò)程以及高級(jí)映射。MyBatis 免除了幾乎所有的 JDBC 代碼以及設(shè)置參數(shù)和獲取結(jié)果集的工作。MyBatis 可以通過(guò)簡(jiǎn)單的 XML 或注解來(lái)配置和映射原始類型、接口和 Java POJO為數(shù)據(jù)庫(kù)中的記錄
        2021-10-10
      • SpringMVC的工程搭建步驟實(shí)現(xiàn)

        SpringMVC的工程搭建步驟實(shí)現(xiàn)

        這篇文章主要介紹了SpringMVC的工程搭建步驟實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
        2021-04-04
      • Java實(shí)現(xiàn)redis分布式鎖的三種方式

        Java實(shí)現(xiàn)redis分布式鎖的三種方式

        本文主要介紹了Java實(shí)現(xiàn)redis分布式鎖的三種方式,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
        2022-08-08
      • Java數(shù)據(jù)結(jié)構(gòu)之哈夫曼樹(shù)概述及實(shí)現(xiàn)

        Java數(shù)據(jù)結(jié)構(gòu)之哈夫曼樹(shù)概述及實(shí)現(xiàn)

        文中詳細(xì)講了關(guān)于Java哈夫曼樹(shù)的概述以及用Java實(shí)現(xiàn)的方法,對(duì)各位正在學(xué)習(xí)java數(shù)據(jù)結(jié)構(gòu)的小伙伴們有很大的幫助喲,需要的朋友可以參考下
        2021-05-05
      • java中Map集合的常用方法總結(jié)大全

        java中Map集合的常用方法總結(jié)大全

        開(kāi)發(fā)中最常用的就是List集合和Map集合,Map集合是基于java核心類java.util中的,下面這篇文章主要給大家總結(jié)介紹了關(guān)于java中Map集合的一些常用方法,文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下
        2024-01-01
      • Java程序死鎖問(wèn)題定位與解決方法

        Java程序死鎖問(wèn)題定位與解決方法

        死鎖是一種特定的程序狀態(tài),主要是由于循環(huán)依賴導(dǎo)致彼此一直處于等待中,而使得程序陷入僵局,相當(dāng)尷尬,死鎖不僅僅發(fā)生在線程之間,而對(duì)于資源獨(dú)占的進(jìn)程之間同樣可能出現(xiàn)死鎖,本文給大家介紹了Java程序死鎖問(wèn)題定位與解決方法,需要的朋友可以參考下
        2024-11-11
      • Spring使用支付寶掃碼支付

        Spring使用支付寶掃碼支付

        這篇文章主要為大家詳細(xì)介紹了Spring使用支付寶掃碼支付的相關(guān)資料,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
        2016-10-10
      • Spring boot actuator端點(diǎn)啟用和暴露操作

        Spring boot actuator端點(diǎn)啟用和暴露操作

        這篇文章主要介紹了Spring boot actuator端點(diǎn)啟用和暴露操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
        2021-07-07
      • 一篇文章帶你入門(mén)java集合

        一篇文章帶你入門(mén)java集合

        Java的集合類型都是對(duì)java.util包中Collection接口的繼承,這里我們主要介紹依賴于collection的一些主分支,一起來(lái)看一下Java中的collection集合類型總結(jié)
        2021-08-08

      最新評(píng)論