其他
硬核!C语言八大排序算法,附动图和详细代码解释!
前言
八大排序算法
1、排序的概念
2、排序分类
3、算法分析
*直接插入排序
*希尔排序
2.选择排序
*简单选择排序
*堆排序
3.交换排序
*冒泡排序
*快速排序
4.归并排序
5.基数排序
不稳定排序:简单选择排序,快速排序,希尔排序,堆排序
稳定排序:冒泡排序,直接插入排序,归并排序,奇数排序
1、插入排序
将第一个和第二个元素排好序,然后将第3个元素插入到已经排好序的元素中,依次类推(插入排序最好的情况就是数组已经有序了)
2、希尔排序
因为插入排序每次只能操作一个元素,效率低。元素个数N,取奇数k=N/2,将下标差值为k的数分为一组(一组元素个数看总元素个数决定),在组内构成有序序列,再取k=k/2,将下标差值为k的数分为一组,构成有序序列,直到k=1,然后再进行直接插入排序。
3、简单选择排序
选出最小的数和第一个数交换,再在剩余的数中又选择最小的和第二个数交换,依次类推
4、堆排序
以升序排序为例,利用小根堆的性质(堆顶元素最小)不断输出最小元素,直到堆中没有元素
1.构建小根堆
2.输出堆顶元素
3.将堆低元素放一个到堆顶,再重新构造成小根堆,再输出堆顶元素,以此类推
5、冒泡排序
改进1:如果某次冒泡不存在数据交换,则说明已经排序好了,可以直接退出排序
改进2:头尾进行冒泡,每次把最大的沉底,最小的浮上去,两边往中间靠1
6、快速排序
选择一个基准元素,比基准元素小的放基准元素的前面,比基准元素大的放基准元素的后面,这种动作叫分区,每次分区都把一个数列分成了两部分,每次分区都使得一个数字有序,然后将基准元素前面部分和后面部分继续分区,一直分区直到分区的区间中只有一个元素的时候,一个元素的序列肯定是有序的嘛,所以最后一个升序的序列就完成啦。
7、归并排序
将一个无序的数列一直一分为二,直到分到序列中只有一个数的时候,这个序列肯定是有序的,因为只有一个数,然后将两个只含有一个数字的序列合并为含有两个数字的有序序列,这样一直进行下去,最后就变成了一个大的有序数列
8、基数排序
找到最大的数,开个比最大的数大一点的数组,遍历每个元素,某个元素为k,则a[k]++,最好遍历数组a,a[k]等于多少就输出多少个k。只能处理整型数
具体排序讲解
void print(int a[], int n ,int i){
cout<<i <<":";
for(int j= 0; j<8; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
void InsertSort(int a[], int n)
{
for(int i= 1; i<n; i++){
if(a[i] < a[i-1]){ //若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入
int j= i-1;
int x = a[i]; //复制为哨兵,即存储待排序元素
a[i] = a[i-1]; //先后移一个元素
while(x < a[j]){ //查找在有序表的插入位置
a[j+1] = a[j];
j--; //元素后移
}
a[j+1] = x; //插入到正确位置
}
print(a,n,i); //打印每趟排序的结果
}
}
int main(){
int a[8] = {3,1,5,7,2,4,9,6};
InsertSort(a,8);
print(a,8,8);
}
void print(int a[], int n ,int i){
cout<<i <<":";
for(int j= 0; j<8; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
/**
* 直接插入排序的一般形式
*
* @param int dk 缩小增量,如果是直接插入排序,dk=1
*
*/
void ShellInsertSort(int a[], int n, int dk)
{
for(int i= dk; i<n; ++i){
if(a[i] < a[i-dk]){ //若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入
int j = i-dk;
int x = a[i]; //复制为哨兵,即存储待排序元素
a[i] = a[i-dk]; //首先后移一个元素
while(x < a[j]){ //查找在有序表的插入位置
a[j+dk] = a[j];
j -= dk; //元素后移
}
a[j+dk] = x; //插入到正确位置
}
print(a, n,i );
}
}
// 先按增量d(n/2,n为要排序数的个数进行希尔排序
void shellSort(int a[], int n){
int dk = n/2;
while( dk >= 1 ){
ShellInsertSort(a, n, dk);
dk = dk/2;
}
}
int main(){
int a[8] = {3,1,5,7,2,4,9,6};
//ShellInsertSort(a,8,1); //直接插入排序
shellSort(a,8); //希尔插入排序
print(a,8,8);
}
从待排序序列中,找到关键字最小的元素; 如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换; 从余下的 N - 1 个元素中,找出关键字最小的元素,重复(1)、(2)步,直到排序结束。因此我们可以发现,简单选择排序也是通过两层循环实现。第一层循环:依次遍历序列当中的每一个元素 第二层循环:将遍历得到的当前元素依次与余下的元素进行比较,符合最小元素的条件,则交换。
void print(int a[], int n ,int i){
cout<<"第"<<i+1 <<"趟 : ";
for(int j= 0; j<8; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
/**
* 数组的最小值
*
* @return int 数组的键值
*/
int SelectMinKey(int a[], int n, int i)
{
int k = i;
for(int j=i+1 ;j< n; ++j) {
if(a[k] > a[j]) k = j;
}
return k;
}
/**
* 选择排序
*
*/
void selectSort(int a[], int n){
int key, tmp;
for(int i = 0; i< n; ++i) {
key = SelectMinKey(a, n,i); //选择最小的元素
if(key != i){
tmp = a[i]; a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换
}
print(a, n , i);
}
}
int main(){
int a[8] = {3,1,5,7,2,4,9,6};
cout<<"初始值:";
for(int j= 0; j<8; j++){
cout<<a[j] <<" ";
}
cout<<endl<<endl;
selectSort(a, 8);
print(a,8,8);
}
void print(int a[], int n){
for(int j= 0; j<n; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
/**
* 已知H[s…m]除了H[s] 外均满足堆的定义
* 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选,
*
* @param H是待调整的堆数组
* @param s是待调整的数组元素的位置
* @param length是数组的长度
*/
void HeapAdjust(int H[],int s, int length)
{
int tmp = H[s];
int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
while (child < length) {
if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
++child ;
}
if(H[s]<H[child]) { // 如果较大的子结点大于父结点
H[s] = H[child]; // 那么把较大的子结点往上移动,替换它的父结点
s = child; // 重新设置s ,即待调整的下一个结点的位置
child = 2*s+1;
} else { // 如果当前待调整结点大于它的左右孩子,则不需要调整,直接退出
break;
}
H[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上
}
print(H,length);
}
/**
* 初始堆进行调整
* 将H[0..length-1]建成堆
* 调整完之后第一个元素是序列的最小的元素
*/
void BuildingHeap(int H[], int length)
{
//最后一个有孩子的节点的位置 i= (length -1) / 2
for (int i = (length -1) / 2 ; i >= 0; --i)
HeapAdjust(H,i,length);
}
/**
* 堆排序算法
*/
void HeapSort(int H[],int length)
{
//初始堆
BuildingHeap(H, length);
//从最后一个元素开始对序列进行调整
for (int i = length - 1; i > 0; --i)
{
//交换堆顶元素H[0]和堆中最后一个元素
int temp = H[i]; H[i] = H[0]; H[0] = temp;
//每次交换堆顶元素和堆中最后一个元素之后,都要对堆进行调整
HeapAdjust(H,0,i);
}
}
int main(){
int H[10] = {3,1,5,7,2,4,9,6,10,8};
cout<<"初始值:";
print(H,10);
HeapSort(H,10);
//selectSort(a, 8);
cout<<"结果:";
print(H,10);
}
void bubbleSort(int a[], int n){
for(int i =0 ; i< n-1; ++i) {
for(int j = 0; j < n-i-1; ++j) {
if(a[j] > a[j+1])
{
int tmp = a[j] ; a[j] = a[j+1] ; a[j+1] = tmp;
}
}
}
}
从数列中挑出一个元素,称为 “基准”(pivot)。 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
void print(int a[], int n){
for(int j= 0; j<n; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int partition(int a[], int low, int high)
{
int privotKey = a[low]; //基准元素
while(low < high){ //从表的两端交替地向中间扫描
while(low < high && a[high] >= privotKey) --high; //从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的交换到低端
swap(&a[low], &a[high]);
while(low < high && a[low] <= privotKey ) ++low;
swap(&a[low], &a[high]);
}
print(a,10);
return low;
}
void quickSort(int a[], int low, int high){
if(low < high){
int privotLoc = partition(a, low, high); //将表一分为二
quickSort(a, low, privotLoc -1); //递归对低子表递归排序
quickSort(a, privotLoc + 1, high); //递归对高子表递归排序
}
}
int main(){
int a[10] = {3,1,5,7,2,4,9,6,10,8};
cout<<"初始值:";
print(a,10);
quickSort(a,0,9);
cout<<"结果:";
print(a,10);
}
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列; 设定两个指针,最初位置分别为两个已经排序序列的起始位置; 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置; 重复步骤3直到某一指针达到序列尾; 将另一序列剩下的所有元素直接复制到合并序列尾。
void print(int a[], int n){
for(int j= 0; j<n; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
int j,k;
for(j=m+1,k=i; i<=m && j <=n ; ++k){
if(r[j] < r[i]) rf[k] = r[j++];
else rf[k] = r[i++];
}
while(i <= m) rf[k++] = r[i++];
while(j <= n) rf[k++] = r[j++];
print(rf,n+1);
}
void MergeSort(ElemType *r, ElemType *rf, int lenght)
{
int len = 1;
ElemType *q = r ;
ElemType *tmp ;
while(len < lenght) {
int s = len;
len = 2 * s ;
int i = 0;
while(i+ len <lenght){
Merge(q, rf, i, i+ s-1, i+ len-1 ); //对等长的两个子表合并
i = i+ len;
}
if(i + s < lenght){
Merge(q, rf, i, i+ s -1, lenght -1); //对不等长的两个子表合并
}
tmp = q; q = rf; rf = tmp; //交换q,rf,以保证下一趟归并时,仍从q 归并到rf
}
}
int main(){
int a[10] = {3,1,5,7,2,4,9,6,10,8};
int b[10];
MergeSort(a, b, 10);
print(b,10);
cout<<"结果:";
print(a,10);
}
八、基数排序(Radix Sort)
d RadixSort(Node L[],length,maxradix)
{
int m,n,k,lsp;
k=1;m=1;
int temp[10][length-1];
Empty(temp); //清空临时空间
while(k<maxradix) //遍历所有关键字
{
for(int i=0;i<length;i++) //分配过程
{
if(L[i]<m)
Temp[0][n]=L[i];
else
Lsp=(L[i]/m)%10; //确定关键字
Temp[lsp][n]=L[i];
n++;
}
CollectElement(L,Temp); //收集
n=0;
m=m*10;
k++;
}
}
使用Python实现
def bubble_sort(numberlist):
length = len(numberlist)
for i in range(length):
for j in range(1, length - i):
if numberlist[j - 1] > numberlist[j]:
numberlist[j], numberlist[j - 1] = numberlist[j - 1], numberlist[j]
return numberlist
def findSmallest(arr): # 用于查找出数组中最小的元素,返回最小元素的索引。
smallest = arr[0]
smallest_index = 0
for i in range(1, len(arr)):
if smallest > arr[i]:
smallest = arr[i]
smallest_index = i
return smallest_index
def selectSort(arr):
newArr = []
while arr:
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
● 取出下一个元素,在已经排序的元素序列中从后向前扫描
● 如果该元素(已排序)大于新元素,将该元素移到下一位置
● 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
● 将新元素插入到该位置后
def insert_sort(data):
for k in range(1, len(data)):
cur = data[k]
j = k
while j > 0 and data[j - 1] > cur:
data[j] = data[j - 1]
j -= 1
data[j] = cur
return data
def shell_sort(numberlist):
length = len(numberlist)
gap = length // 2
while gap > 0:
for i in range(gap, length):
temp = numberlist[i]
j = i
while j >= gap and numberlist[j - gap] > temp:
numberlist[j] = numberlist[j - gap]
j -= gap
numberlist[j] = temp
gap = gap // 2
return numberlist
def merge(left, right):
result = []
while left and right:
if left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
if left:
result += left
if right:
result += right
return result
def merge_sort(numberlist):
if len(numberlist) <= 1:
return numberlist
mid = len(numberlist) // 2
left = numberlist[:mid]
right = numberlist[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
def quick_sort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
def heap_sort(numberlist):
length = len(numberlist)
def sift_down(start, end):
root = start
while True:
child = 2 * root + 1
if child > end:
break
if child + 1 <= end and numberlist[child] < numberlist[child + 1]:
child += 1
if numberlist[root] < numberlist[child]:
numberlist[root], numberlist[child] = numberlist[child], numberlist[root]
root = child
else:
break
# 创建最大堆
for start in range((length - 2) // 2, -1, -1):
sift_down(start, length - 1)
# 堆排序
for end in range(length - 1, 0, -1):
numberlist[0], numberlist[end] = numberlist[end], numberlist[0]
sift_down(0, end - 1)
return numberlist
def counting_sort(numberlist, maxnumber): # maxnumber为数组中的最大值
length = len(numberlist) # 待排序数组长度
b = [0 for i in range(length)] # 设置输出序列,初始化为0
c = [0 for i in range(maxnumber+ 1)] # 设置技术序列,初始化为0
for j in numberlist:
c[j] = c[j] + 1
for i in range(1, len(c)):
c[i] = c[i] + c[i - 1]
for j in numberlist:
b[c[j] - 1] = j
c[j] = c[j] - 1
return b
基数排序,此外还有桶、箱排序。
热 文 推 荐
☞2019女性开发者报告:3成16岁就会编程、JS/Python成女性掌握最多语言
☞我国自主开发的编程语言“木兰”是又一个披着“洋”皮的红芯浏览器吗?