排序算法:选择排序,插入排序与希尔排序

收藏到CSDN网摘
常用排序算法之:选择排序,插入排序与希尔排序

这是非常经典的3个排序算法,在各种acm题目和日常编程中时有使用.

1. 选择排序: (SelectionSort)
方法: 从左向右移动当前下标[],始终将当前元素与右边的最小值交换
特点: []左边为已经排序好的元素,右边没有比左边小的元素(否则已经被交换)

2. 插入排序: (InsertionSort)
方法: 从左向右移动当前下标[],始终将当前元素与左边每一个比它大的值交换(从左边第一个开始比较,如果比左边大,直接break内层循环,因为左边已经排序好)
特点: []左边为已经排序好的元素,右边为尚未检测的元素.

3. 希尔排序: (ShellSort)
方法: 用一个增量序列h(其实是递减的)来对原数组做h-sorting,直到h==1(这时就是插入排序)
特点: 是插入排序的改进版本,高效且稳定.一个很好的理解方法是:将原序列按照h个一行排列,然后对每一"列"排序后,从新连接起来;一直到h==1结束.
增量序列的选择: 经过实践检验,增量序列的选择直接影响希尔排序的性能,最开始一般选择2^n,后来有各种不同的改进(目前仍是一个开放问题).实践中一般选择3x+1序列.
目前最优序列是Sedgewick提出的: 1 5 19 41 109 209 505 929 2161 3905 ...
这个序列是由这2个序列的元素交替排列而来: 9*4^x - 9*2^x +1 和 4^x - 3*2^x + 1

下面是python实现的这3种排序算法及测试:

#! /usr/bin/env python
# coding: utf-8

def SelectionSort(s):
    '''
    Selection sort: [] from left to right,
    exchange [] with the min value on its right
    '''
    print 'Selection Sorting Algorithm:'
    print 'Original\t', ' '.join([str(x) for x in s])
    for i in range(len(s)):
        if s[i+1:]:
            m = min(s[i+1:])
            if s[i]<m:
                continue
            ind = i+1+s[i+1:].index(m)
            s[i], s[ind] = s[ind], s[i]
            print 'exch[', i+1, ']\t', ' '.join([str(x) for x in s])
    print 'Sorted\t\t', ' '.join([str(x) for x in s])
    return s

def InsertionSort(s):
    '''
    Insertion sort: [] from left to right,
    exchange [] with each bigger value on its left
    '''
    print 'Insertion Sorting Algorithm:'
    print 'Original\t', ' '.join([str(x) for x in s])
    cnt = 1
    for i in range(1,len(s)):
        for j in range(i,0,-1):
            if s[j]<s[j-1]:
                s[j], s[j-1] = s[j-1], s[j]
                print 'exch[', cnt, ']\t', ' '.join([str(x) for x in s])
                cnt += 1
            else:
                break
    print 'Sorted\t\t', ' '.join([str(x) for x in s])
    return s

def ShellSort(s):
    '''
    Shell sort: perform h-sorting over the sequence,
    h is an increamental sequence, 3x+1 is good
    but the best is Sedgewick one: 1 5 19 41 109 209 505 929 2161 3905
    which can be produced by merging 9*4^i-9*2^i+1 and 4^i-3*2^i+1
    '''
    print 'Shell Sorting Algorithm:'
    print 'Original\t', ' '.join([str(x) for x in s])
    h = 1
    while h<len(s)/3:
        h = 3*h+1;
    while h>=1:
        print 'h =', h
        cnt = 1
        for i in range(h,len(s)):
            for j in range(i,-1,-h):
                if j>=h and s[j]<s[j-h]:
                    s[j], s[j-h] = s[j-h], s[j]
                    print 'exch[', cnt, ']\t', ' '.join([str(x) for x in s])
                    cnt += 1
        h /= 3
    print 'Sorted\t\t', ' '.join([str(x) for x in s])
    return s
    
def main():
    a = '52 50 99 47 59 96 45 72 58 40'
    s = [int(x) for x in a.split(' ')]
    SelectionSort(s)

    print '='*20
    a = '43 46 53 77 87 51 65 25 21 18'
    s = [int(x) for x in a.split(' ')]
    InsertionSort(s)

    print '='*20
    a = '83 87 36 53 16 14 97 51 52 44'
    s = [int(x) for x in a.split(' ')]
    ShellSort(s)

if __name__=='__main__':
    main()
        
        

一个详细讲解及比较排序算法的网站在这里.