排序算法

Cloud-Cloudys

发布于 2020-07-07 16:08:10

3490

发布于 2020-07-07 16:08:10

稳定的直接插入排序

基本思想: 我们将一个待排序序列分为有序区和无序区（一般开始的时候将第一个元素作为有序区，剩下的元素作为无序区），每次将无序区的第一个元素作为待插入记录，按大小插入到前面已经排好的有序区中的适当位置，直到记录全部插入完成为止。(如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面)

C++ 实现

void insert_sort_1(int a[],int n)//对n个元素从小到大排序
{
	int i,j;
	int temp;
	for(i=1;i<n;i++)
	{
		temp = a[i];//待插入元素
		j = i-1;
		while(temp<a[j] && j)
		{
			a[j+1] = a[j];//将大的往后挪
			j--;//顺利的话可以减到-1，要么就是减到可以插入的位置的前一个位置
			    //所以后面的j需要加1
		}
		a[j+1]=temp;
	}
}

Python 实现

def insert_sort(arr: List[int], n: int) -> None:
    for i in range(1, n):
        j: int = i - 1
        wait_insert_ele: int = arr[i]
        while j >= 0:
            if arr[j] > wait_insert_ele:
                arr[j+1] = arr[j]  # 将大于待插入元素的往后移
            else:
                break
            j -= 1
        arr[j + 1] = wait_insert_ele  # 插入数据

稳定的冒泡排序

基本思想: 我们把待排序元素序列竖直放置，每趟对相邻的元素进行两两比较，顺序相反则进行交换，每趟会将最小或最大的元素“浮”到元素序列的顶端，最终元素序列达到有序

实现示例

void bubble_sort(int array[],int n)// 对 n 个数从小到大排序，注意数组下标从 0 开始
{
	int i,j;
	int temp;
	for(i=0;i<n-1;i++)// 进行 n-1 趟比较
	{
		for(j=0;j<n-1-i;j++)// 每趟进行 n-1-i 次比较
		{
			if(array[j+1]<array[j])
			{
			    temp = 	array[j+1];
			    array[j+1] = array[j];
			    array[j] = temp;
			}
		}
	}
}

优化（一但有一趟不需要比较，就表明可以结束了）

def bubble_sort(arr: List[int], n: int) -> None:
    for i in range(n):
        flag: bool = False  # 标记某趟是否还需要比较
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j+1], arr[j] = arr[j], arr[j+1]
                flag = True
        if not flag:  # 一但有一趟不需要比较，就表明可以结束了
            break

不稳定的快速排序

快速排序是分治思想在排序算法上的应用，从本质上来讲快速排序应该是在冒泡排序基础上的递归分治法。

算法步骤:

从待排数列中选出一个元素作为基准，一般选第一个元素
重新排序待排数列，所有元素比基准小的摆放在基准前面，所有元素比基准大的摆放在基准后面（相同的数可以放在任意一边）。在这个分区退出后，该基准就处于中间位置。（这个即为分区操作(partion)）。
递归地把小于基准元素的子数列和大于基准元素的子数列进行排序。

实现

def quick_sort(arr: List[int], left: int, right: int) -> None:
    if left >= right:
        return

    index = partition(arr, left, right)
    quick_sort(arr, left, index - 1)
    quick_sort(arr, index + 1, right)


def partition(arr: List[int], left: int, right: int) -> None:
    pivot = arr[right]
    index = left
    for j in range(left, right):
        if arr[j] < pivot:
            arr[j], arr[index] = arr[index], arr[j]
            index += 1
    arr[index], arr[right] = arr[right], arr[index]
    return index

另类 C 实现

#include<stdio.h>
int a[101],n;

void quick_sort(int left, int right)
{
	int i,j,temp;
	int t;
	if(left > right)
	{
		return ;
	}

	temp = a[left];//基准数


	i = left;
	j = right;
	while(i != j)
	{
		//顺序很重要，先从右往左找
	    while( a[j] >= temp && i<j)
		{
			j--;
		}

		//再从左边往右找
		while( a[j] <= temp && i<j)
		{
			i++;
	    }

	    //交换两个数在数组中的位置
		if(i<j)//两个哨兵没有相遇
		{
			t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
	}

	//最终将基准数归位,

	a[left] = a[i];

	a[i] = temp;//归位

	quick_sort(left,i-1);//继续处理左边的数
	quick_sort(i+1,right);//继续处理右边的数

	return ;
}

int main()
{
	int i,j;
	scanf("%d",&n);
	for(i=1; i<=n; i++)//下表从1开始
	    scanf("%d",&a[i]);

	quick_sort(1,n);//sort

	for(j=1; j<=n; j++)
	    printf("%d ",a[j]);

	return 0;
}