程序员面试必备之排序算法汇总(上)

2021-12-18 02:20:18

本文用Python实现了快速排序、插入排序、希尔排序、归并排序、堆排序、选择排序、冒泡排序共7种排序算法。

程序员面试必备之排序算法汇总(上)

一、快速排序

1.介绍

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

2.步骤及流程图

(1)从数列中挑出一个元素，称“基准”

(2)重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

(3)递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

流程图：（字很丑~后边还是不画了哈）

程序员面试必备之排序算法汇总(上)

3.python实现

#encoding=utf-8
import random   
#快速排序  
def qsort(list,low,high):    
    if low >= high:  
        return  
    first=low  
    last=high  
    key=list[first]  
#主循环，算法重点，见流程图  
    while last>first:  
        while last>first and list[last] >= key:  
            last-=1  
        list[first]=list[last]  
        while last>first and list[first] <= key:  
            first+=1  
        list[last]=list[first]  
    list[first]=key  
#这两行利用递归完成两个分区的排序
    qsort(list,low,first-1)       
    qsort(list,first+1,high)  
#以下是调用快速排序方法
my_list=[]  
for i in range(8):  
    my_list.append(random.randint(1,300))  
qsort(my_list,0,len(my_list)-1)  
print(my_list)

4.视觉效果展示

二、插入排序

1.介绍

插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

2.步骤

(1)从第一个元素开始，该元素可以认为已经被排序

(2)取出下一个元素，在已经排序的元素序列中从后向前扫描

(3)如果该元素（已排序）大于新元素，将该元素移到下一位置

(4)重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

(5)将新元素插入到该位置中

(6)重复步骤2

3.python实现

#encoding=utf-8
import random 
# 插入排序  
def insert_sort(lists):
    count = len(lists)
    for i in range(1, count):
#取下一个元素到key
        key = lists[i]
        j = i - 1
        while j >= 0:
#找到新元素（key）的正确位置
            if lists[j] > key:
                lists[j + 1] = lists[j]
                lists[j] = key
            j -= 1
    return lists
#调用插入排序方法  
my_list=[]  
for i in range(8):  
    my_list.append(random.randint(1,300))  
insert_sort(my_list)  
print(my_list)

三、希尔排序

1.介绍

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

2.python实现（小詹写的运行过程出了点错，先借用下别人的小程序哈）

#encoding=utf-8
# 希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
# 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
# 希尔排序是基于插入排序的以下两点性质而提出改进方法的：
# 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
# 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
def ShellInsetSort(array, len_array, dk):  # 直接插入排序
    for i in range(dk, len_array):  # 从下标为dk的数进行插入排序
        position = i
        current_val = array[position]  # 要插入的数
        index = i
        j = int(index / dk)  # index与dk的商
        index = index - j * dk
        # while True:  # 找到第一个的下标，在增量为dk中，第一个的下标index必然 0<=index<dk< span="">
        #     index = index - dk
        #     if 0<=index and index <dk:< span="">
        #         break
        # position>index,要插入的数的下标必须得大于第一个下标
        while position > index and current_val < array[position-dk]:
            array[position] = array[position-dk]  # 往后移动
            position = position-dk
        else:
            array[position] = current_val
def ShellSort(array, len_array):  # 希尔排序
    dk = int(len_array/2)  # 增量
    while(dk >= 1):
        ShellInsetSort(array, len_array, dk)
        print(">>:",array)
        dk = int(dk/2)
if __name__ == "__main__":
    array = [49, 38, 65, 97, 76, 13, 27, 49, 55, 4]
    print(">:", array)
    ShellSort(array, len(array))
</dk:<></dk<>

3.视觉效果展示

以上就是本期的内容，欢迎小伙伴们扫码订阅点赞噢~

码农公寓

相关文章