經典排序算法 - 插入排序 - 52fhy－IT工程師數位筆記本

文章出處

概述

插入排序就是每一步都將一個待排數據按其大小插入到已經排序的數據中的適當位置，直到全部插入完畢。

插入排序方法分直接插入排序和折半插入排序兩種，這里只介紹直接插入排序，折半插入排序留到“查找”內容中進行。

題目：給出無需數組 [4,3,1,2]，要求按照從小到大使用插入排序法排序。
輸出樣例：

解題思路：
1) 先固定住第一個元素，第二個元素與第一個元素比較，若小于第一個元素則交換位置；
2) 將第三個元素與前面2個元素依次比較，若小于則插入被比較的元素前面；
3) 將第四個元素與前面3個元素依次比較，若小于則插入被比較的元素前面。

C語言實現

#include<stdio.h>

#define MAX 4
void insertion_sort(int *, int);

int main(){
    
    
    int arr[MAX] = {4,3,1,2};   
    insertion_sort(arr, MAX);
    
    int i;
    for(i =0; i< MAX; i++){
        printf("%d\n", arr[i]);
    }
    
    return 0;
}

void insertion_sort(int *arr, int n){
    int i,j,temp;
    for(i=1; i< n; i++){
        if(arr[i-1] > arr[i]){
            j = i;
            temp = arr[j];
            while(j>0 && arr[j-1] > temp){
                arr[j] = arr[j-1];
                j--;
            }
            arr[j] = temp;
        }
    }
}

PHP實現

$arr = [4,3,1,2];

//1,3,4,2

function insertion_sort(&$arr){
    $len = count($arr);
    for($i= 1; $i < $len; $i++){
        if($arr[$i-1] > $arr[$i]){
            $j = $i;
            $temp = $arr[$i];//暫存這個需要插隊的元素
            while ($j > 0 && $arr[$j-1] > $temp){//將插隊元素前面的每一個元素與該元素對比
                $arr[$j] = $arr[$j-1];//大于該插隊元素的往后面挪一位
                $j--;
            }
            $arr[$j] = $temp;//找到合適位置，插隊結束
        }
    }
}

insertion_sort($arr);
print_r($arr);