基本思想: 我们将一个待排序序列分为有序区和无序区(一般开始的时候将第一个元素作为有序区,剩下的元素作为无序区),每次将无序区的第一个元素作为待插入记录,按大小插入到前面已经排好的有序区中的适当位置,直到记录全部插入完成为止。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面)
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
快速排序是分治思想在排序算法上的应用,从本质上来讲快速排序应该是在冒泡排序基础上的递归分治法。
算法步骤:
实现
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;
}