插入排序和冒泡排序

1、插入排序

• 流程如下：

1）从第一个元素开始遍历，该元素可以认为已经被排序，记录已排序序列的结尾元素为end = i
2）取下一个元素temp = arr[end + 1]，从已排序的元素序列从后往前遍历
3）如果遍历的元素arr[end]> temp，则将该元素移到下一位，即arr[end+1] = arr[end]，同时end–
4）如果遍历的元素arr[end]<= temp，则跳出循环
5）将temp插入到该元素的后面，即arr[end + 1] = temp

• C++代码为：

#include 
using namespace std;

void insert_sort(vector<int>& arr){
	int n = arr.size();
	for (int i = 1; i < n; i++){
		end = i - 1;
		temp = arr[i];
		while (end >= 0 && arr[end] > temp){
			arr[end+1] = arr[end];
			end--;
		}
		arr[end + 1] = temp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• Python：

def insertion_sort(arr):
    for i in range(1, len(arr)):
        temp = arr[i]  # 当前待插入的元素
        end = i - 1  # 已排序部分的最后一个元素的索引位置

        while end >= 0 and arr[end] > temp:
            arr[end + 1] = arr[end]  # 把比当前元素大的元素往后移动
            end -= 1

        arr[end + 1] = temp  # 插入当前元素到正确的位置

    return arr

1
2
3
4
5
6
7
8
9
10
11
12
13

2、冒泡排序

• 流程如下：

1）从第一个元素开始，比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2）那么最后的元素应该会是最大的数。
3）持续每次对越来越少的元素重复上面的步骤，重复n = arr.size()次，直到没有任何一对数字需要比较。

• C++：

#include 
using namespace std;

void bubble_sort(vector<int>& arr){
	int n = arr.size();
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n - i -1; j++){
			if (arr[j] > arr[j+1]){
				int temp = arr[j+1];
				arr[j+1] = arr[j];
				arr[j] = temp;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• Python:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                temp = arr[j + 1]
                arr[j + 1] = arr[j]
                arr[j] = temp
1
2
3
4
5
6
7
8

3、选择排序

• 基本思想是在未排序的序列中选择最小的元素，然后将其放到已排序的序列的前面。重复这个过程，直到所有的元素都被排序为止。

def select_sort(arr):
    n = len(arr)
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr
1
2
3
4
5
6
7
8
9

4、快速排序

• 基本思想是通过一次划分操作将待排序数据分割成独立的两部分，其中一部分的所有元素都比另一部分的所有元素小，再对这两部分分别进行快速排序，从而让整个序列达到有序。

def quick_sort(arr, left, right):
    if left < right:
        idx = partition(arr, left, right)
        quick_sort(arr, left, idx-1)
        quick_sort(arr, idx+1, right)
    return arr


def partition(arr, left, right):
    key = left
    while left < right:
        while left < right and arr[right] >= arr[key]:
            right -= 1
        while left < right and arr[left] <= arr[key]:
            left += 1
        arr[left], arr[right] = arr[right], arr[left]
    arr[key], arr[left] = arr[left], arr[key]
    return left
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5、归并排序

• 归并排序是建立在归并操作上的一种有效的排序算法。

1）把长度为n的输入序列分成两个长度为n/2的子序列；
2）对这两个子序列分别采用归并排序；
3）将两个排序好的子序列合并成一个最终的排序序列。

#递归调用归并排序
def mSort(arr,left,right):
    if left>=right:
        return
    mid=(left+right)//2
    mSort(arr,left,mid)
    mSort(arr,mid+1,right)
    merge(arr,left,mid,right)

# 合并左右子序列函数
def merge(arr,left,mid,right):
    temp=[]     #中间数组
    i=left          #左段子序列起始
    j=mid+1   #右段子序列起始
    while i<=mid and j<=right:
        if arr[i]<=arr[j]:
            temp.append(arr[i])
            i+=1
        else:
            temp.append(arr[j])
            j+=1
    while i<=mid:
        temp.append(arr[i])
        i+=1
    while j<=right:
        temp.append(arr[j])
        j+=1
    for i in range(left,right+1):    #  !注意这里，不能直接arr=temp,他俩大小都不一定一样
        arr[i]=temp[i-left]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

6、堆排序

• 过程如下：

1）将arr调整成大根堆
2）将首元素（待排序列的最大值）与待排序列尾元素交换
3）调整剩余元素为大根堆
4）重复上述过程

def heap_sort(array):
    n=len(array)
    build_heap(array)
    #每轮循环抛出一个待排序列的最大值。
    for i in range(n-1,0,-1):
        array[i],array[0]=array[0],array[i]
        down(array,0,i)
        
def build_heap(array):
    n=len(array)
    #从最后一个有孩子的节点（深度为2）开始遍历到根节点，每个节点掉用一次perc_down函数向下过滤
    for parent in range(n//2-1,-1,-1):
      down(array,parent,n)  

#向下过滤函数，array为待排序序列，parent为根节点的索引值，lenth为待排序序列长度
def down(array,parent,lenth):
#如果待排序序列长度小于等于1 则不用排序
    if lenth<=1:	
        return
    child=parent*2+1	#左孩子索引
    while True:
    	#判断是否有右孩子，若有让左右孩子中最大值的索引赋给child
        if child != lenth - 1 and array[child] < array[child + 1]:	 #若要最小堆 此处 < 改成 >
            child += 1
        #再比较父节点的值与孩子中最大的值，保证将最大值放在父节点的位置
        if array[child] > array[parent]:					#若要最小堆 此处 > 改成 <
            array[child], array[parent] = array[parent], array[child]
        if (child + 1) * 2 > lenth:						#值最大的孩子为叶子节点时，不再向下比较
            return
        parent, child = child, child * 2 + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

https://blog.csdn.net/weixin_41571493/article/details/81875088