排序算法--插入排序

发表于

排序算法有内部排序和外部排序， 内部排序是数据记录在内存中进行排序， 而外部排序是因排序的数据很大， 一次不能容纳全部排序记录， 在排序过程中要访问外存。本文的八大排序是内部排序。

1、直接插入排序

使用java实现：

1
2
3
4
5
6
7
8
9
10
11
12
public static void insertsort(int arr[]){
    for(int i = 1; i<arr.length; i++){
        if(arr[i] < arr[i-1]){
            int temp = arr[i];
            int j;
            for(j = i-1; j>00&&arr[j]>temp; j--){
                arr[j+1] = arr[j];
            }
            arr[j+1] = temp;
        }
    }
}

使用python实现

1
2
3
4
5
6
7
8
9
10
def insertsort(arr):
    for i in range(len(l)):
        temp = arr[i]
        j = i
        while j>0 and temp<arr[j-1]:
            arr[j] = arr[j-1]
        
        arr[j] = temp
    return arr

使用javascript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
function insertsort(arr){
    for(var i=1; i<arr.length; i++){
        var temp = arr[i];
        var j;
        for(j = i-1; j>=0&&arr[j]>temp; j--){
            arr[j+1] = arr[j];
        }
        arr[j] = temp;
    }
    return arr;
}

2、希尔排序

希尔(shell)排序又称为缩小增量排序，他是一种插入排序。是直接插入排序算法的一种威力加强版。该方法因DL.Shell于1959年提出而得名。
希尔排序的基本思想是：
1、把记录按步长gap分组，对于每组记录采用直接插入排序方法进行排序。
2、随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到1时，整个数据合成为一组。构成一组有序记录完成排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void shellSort(int[] list){
    int gap = list.length/2;
    while(1<=gap){
        for(int i = gap; i<list.length; i++){
            int temp = a[i];  
            int k = i - gap;  
            while (k >= 0 && a[k] > temp)  
            {  
                a[k + gap] = a[k];  
                k -= gap;  
            }  
            a[k + gap] = temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
# coding:utf-8
def shellSort(nums):
#设定步长
    step = len(nums)/2
    while step>0:
        for i in range(step, len(nums)):
            while i>=step and nums[i-step] > nums[i]:
                nums[i],nums[i-step] = nums[i-step],nums[i]
                i -= step
        step = step/2
    return nums
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function shellSort(nums){
    
    for(var step=nums.lengh/2;step>0;step=step/2){
        for(var i=step;i<nums.length;i++){
            var temp = nums[i];
            int k = i - gap;
            while(k>=0&&nums[k]>temp){
                
                nums[k] = nums[k-step];
                k -=step;
            }
            a[k+gap] = temp;
        }
    } 
}