首页 > 代码库 > 数据结构--插入排序

数据结构--插入排序

2024-07-28 21:51:44   221人阅读

插入排序算法主要有三种：直接插入排序、折半插入排序、希尔排序

1、直接插入排序：

/**
  * 直接插入排序,
  * 1、从i-->length-1开始做插入扫描
  * 2、初始化一个要插入的元素（1步骤中的）
  * 3、从0-->i开始做插入排序操作
  *      如果要插入的元素小于0-->i中的某一个元素，则做位置替换，
  *      否者，执行第一步（i+1）步骤
  * 4、结束
  * 时间复杂度:∑(i+1)/2 = (n2+3n+4)/4 =~ n2 ,(1<=i<=n);
  * 空间复杂度:需要一个空间地址作交换，故O(1);
  */

def StraightInsertionSort(list):

    for i in range(1, len(list)):
        for j in range(i, 0, -1):
            if list[j] < list[j - 1]:
                tmp = list[j - 1]
                list[j - 1] = list[j]
                list[j] = tmp
        print list
    return list

2、折半插入排序

/**
  * 折半插入排序
  * 1、从i-->length-1开始做插入扫描
  * 2、初始化一个要插入的元素（1步骤中的）
  * 3、从0-->i开始做折半查找插入操作
  *  a、通过折半的方式定位要插入的元素的位置X 
  *   b、将位置X及以后的元素往后移动一位
  *   c、将位置X赋值为要插入的元素
  * 4、结束
  * 时间复杂度:∑(i+1)/2 = (n2+3n+4)/4 =~ n2 ,(1<=i<=n);
  * 空间复杂度:需要一个空间地址作交换，故O(1);
  */
def BinaryInsertionSort(list):

    for i in range(1, len(list)):
        low = 0
        high = i
        tmp = list[i]
        while low <= high:
            mid = (low + high) / 2
            if list[mid] > tmp:     
                high = mid - 1
            else:
                low = mid + 1
        """this line is special, bucause python‘s list can be get [-2] element"""
        if i - 1 <= high:continue
        """find the high tag, then remove j - 1 --> j, last reset index [high + 1] element to tmp"""
        for j in range(i, high + 1, -1):
            list[j] = list[j - 1]
        list[high + 1] = tmp
        print list
    return list

 

3、希尔排序

"""
delta = 10 / 2 = 5
49   38   65   97   26   13   27   49   55   4
1A                       1B
     2A                       2B
          3A                       3B
               4A                       4B
                    5A                       5B
 
delta = 5 / 2 = 2
13   27   49   55   4    49   38   65   97   26
1A        1B        1C        1D        1E
     2A        2B        2C        2D        2E
 
delta = 2 / 2 = 1
4   26   13   27   38    49   49   55   97   65
1A  1B   1C   1D   1E    1F   1G   1H   1I   1J
 
delta = 1 / 2 = 0
4   13   26   27   38    49   49   55   65   97
 
"""
 
def shellSort(list):
    delta = len(list)
    while delta / 2 > 0:
        delta = delta / 2
        for i in range(delta, len(list)):
            tmp = list[i]
            j = i - delta
            while j >= 0 and tmp < list[j]:
                list[j + delta] = list[j]  
                j -= delta
            list[j + delta] = tmp
        print list
    return list

 

数据结构--插入排序


联系
我们