稳定的直接插入排序

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

插入排序

C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 实现

1
2
3
4
5
6
7
8
9
10
11
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 # 插入数据

稳定的冒泡排序

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

冒泡排序示例

实现示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}
}
}
}

优化(一但有一趟不需要比较,就表明可以结束了)

1
2
3
4
5
6
7
8
9
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

不稳定的快速排序

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

算法步骤:

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

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

快排示例

quickSort.gif

另类 C 实现

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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;
}

参考

评论