Java實現插入排序,希爾排序和歸并排序
更新時間：2022年12月22日 11:05:37 作者：程序小猿2
這篇文章主要為大家詳細介紹了插入排序,希爾排序和歸并排序的多種語言的實現（JavaScript、Python、Go語言、Java），感興趣的小伙伴可以了解一下
插入排序
插入排序的代碼實現雖然沒有冒泡排序和選擇排序那么簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。插入排序是一種最簡單直觀的排序算法，它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。
插入排序和冒泡排序一樣，也有一種優(yōu)化算法，叫做拆半插入。
算法步驟
1.將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列。
2.從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。）
動圖演示
JavaScript代碼實現
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代碼實現
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代碼實現
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代碼實現
public class InsertSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
//對arr進行拷貝，不改變參數內容
int[] arr = Array.copyOf(sourceArray,sourceArray.length);
//從下標為1的元素開始選擇合適的位置插入，因為下標為0的只有一個元素，默認是有序的
for(int i = 1;i < arr.length;i++{
//記錄要插入的數據
int temp = arr[i];
//從已經排序的序列最右邊開始比較，找到比其小的數
int j = i;
while(j > 0 && temp < arr[j - 1] {
arr[j] = arr[j-1];
j--;
}
//存在比其小的數，插入
if(j != i){
arr[j] = temp;
}
}
return arr;
}
} 希爾排序
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩(wěn)定排序算法。
希爾排序是基于插入排序以下兩點性質而提出改進方法的：
- 插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率；
- 但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位；
希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。
算法步驟
- 選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
- 按增量序列個數 k，對序列進行 k 趟排序；
- 每趟排序，根據對應的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
JavaScript代碼實現
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/3) { //動態(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代碼實現
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代碼實現
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代碼實現
public class ShellSort implements IArraySort{
@Override
public int[] sort(int[] sourceArray) throws Exception{
//對arr進行拷貝，不改變參數內容
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）的一個非常典型的應用。
作為一種典型的分而治之思想的算法應用，歸并排序的實現由兩種方法：
- 自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）；
- 自下而上的迭代；
在《數據結構與算法 JavaScript 描述》中，作者給出了自下而上的迭代方法。但是對于遞歸法，作者卻認為：
However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
然而，在 JavaScript 中這種方式不太可行，因為這個算法的遞歸深度對它來講太深了。
說實話，我不太理解這句話。意思是 JavaScript 編譯器內存太小，遞歸太深容易造成內存溢出嗎？還望有大神能夠指教。
和選擇排序一樣，歸并排序的性能不受輸入數據的影響，但表現比選擇排序好的多，因為始終都是 O(nlogn) 的時間復雜度。代價是需要額外的內存空間。
算法步驟
1.申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列；
2.設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；
3.比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；
4.重復步驟 3 直到某一指針達到序列尾；
5.將另一序列剩下的所有元素直接復制到合并序列尾。
動圖演示
JavaScript代碼實現
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代碼實現
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代碼實現
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代碼實現
public class MergeSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝，不改變參數內容
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實現插入排序,希爾排序和歸并排序的詳細內容，更多關于Java排序的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要介紹了idea在運行期間,實現讓修改的頁面實時生效問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-01-01
Java Mybatis框架增刪查改與核心配置詳解流程與用法
MyBatis 是一款優(yōu)秀的持久層框架，它支持自定義 SQL、存儲過程以及高級映射。MyBatis 免除了幾乎所有的 JDBC 代碼以及設置參數和獲取結果集的工作。MyBatis 可以通過簡單的 XML 或注解來配置和映射原始類型、接口和 Java POJO為數據庫中的記錄2021-10-10
這篇文章主要介紹了SpringMVC的工程搭建步驟實現，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-04-04
本文主要介紹了Java實現redis分布式鎖的三種方式，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-08-08
文中詳細講了關于Java哈夫曼樹的概述以及用Java實現的方法,對各位正在學習java數據結構的小伙伴們有很大的幫助喲,需要的朋友可以參考下2021-05-05
開發(fā)中最常用的就是List集合和Map集合,Map集合是基于java核心類java.util中的,下面這篇文章主要給大家總結介紹了關于java中Map集合的一些常用方法,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2024-01-01
死鎖是一種特定的程序狀態(tài),主要是由于循環(huán)依賴導致彼此一直處于等待中,而使得程序陷入僵局,相當尷尬,死鎖不僅僅發(fā)生在線程之間,而對于資源獨占的進程之間同樣可能出現死鎖,本文給大家介紹了Java程序死鎖問題定位與解決方法,需要的朋友可以參考下2024-11-11
這篇文章主要為大家詳細介紹了Spring使用支付寶掃碼支付的相關資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-10-10
這篇文章主要介紹了Spring boot actuator端點啟用和暴露操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-07-07
Java的集合類型都是對java.util包中Collection接口的繼承,這里我們主要介紹依賴于collection的一些主分支,一起來看一下Java中的collection集合類型總結2021-08-08