经典排序算法 - 插入排序

@date:2017-07-22 21:54:00

概述 #

插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕。

插入排序方法分直接插入排序和折半插入排序两种,这里只介绍直接插入排序,折半插入排序留到“查找”内容中进行。

题目:给出无需数组 [4,3,1,2],要求按照从小到大使用插入排序法排序。
输出样例:

1
2
3
4

解题思路:

  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);

若需从大到小排序,只需要将if($arr[$i-1] > $arr[$i]){$arr[$j-1] > $temp改为小于号。

参考:
经典排序算法 – 插入排序Insertion sort - kkun - 博客园
http://www.cnblogs.com/kkun/archive/2011/11/23/2260265.html

Build by Loppo 0.6.14