数据结构与算法 4:排序算法,选择/插入/冒泡/希尔/快速/归并

程序员文章站 2022-03-12 16:01:10

...

【本文谢绝转载，原文来自http://990487026.blog.51cto.com】

排序算法平均复杂度

冒泡排序 O(n2)

选择排序 O(n2)

插入排序 O(n2)

希尔排序 O(n1.5)

快速排序 O(N*logN)

归并排序 O(N*logN)

堆排序 O(N*logN)

基数排序 O(d(n+r))

选择排序:

aaa@qq.com://990487026.blog.51cto.com~/sort$ cat main.c 
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

void printArray01(int array[], int len)
{
	int i = 0;
	for(i=0; i<len; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
}

void swap01(int array[], int i, int j)
{
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

void SelectionSort(int array[], int len) // O(n*n)
{
	int i = 0;
	int j = 0;
	int k = -1;

	for(i=0; i<len; i++)
	{
		k = i; //寻找最小元素的下标
		for(j=i+1; j<len; j++)
		{
			if( array[j] < array[k] ) //开始寻找最小元素的下标
			{
				k = j;	
			}
		}
		swap01(array, i, k);
	}
}

int main()
{
	int array[] = {12, 5, 433, 253, 216, 7};
	int len = sizeof(array) / sizeof(*array); 

	printArray01(array, len);
	SelectionSort(array, len);
	printArray01(array, len);
	return 0;
}

aaa@qq.com://990487026.blog.51cto.com~/sort$ gcc main.c -Wall && ./a.out 
12 5 433 253 216 7 
5 7 12 216 253 433 
aaa@qq.com://990487026.blog.51cto.com~/sort$

插入法排序:

aaa@qq.com://990487026.blog.51cto.com~/sort$ cat main.c 
#include <stdio.h>
void insert_sort(int *arr,int len)//时间复杂度 O^2
{
	int i = 0;
	int j = 0;
	int k = 0;
	int t = -1;
	for(i=1;i<len;i++)
	{
		k=i;//待插入位置
		t=arr[k];
		for(j=i-1;(j>=0 && (arr[j]>t));j--)
		{
			arr[j+1]  =arr[j];//元素往后移动
			k = j;		//k  需要插入的位置
		}
		arr[k] = t;	//元素插入
	}
}

void print_arr(int *arr,int len)
{
	int i = 0;
	for(i=0;i<len;i++)	
	{
		printf("%d ",*(arr+i));
	}
	printf("\n");
}

int main()
{
	int arr[] = {12,55,66,11,22,1,99,2,7};
	print_arr(arr,sizeof(arr)/sizeof(int));
	insert_sort(arr,sizeof(arr)/sizeof(int));
	print_arr(arr,sizeof(arr)/sizeof(int));
	

	return 0;
}
aaa@qq.com://990487026.blog.51cto.com~/sort$ gcc main.c -Wall && ./a.out 
12 55 66 11 22 1 99 2 7 
1 2 7 11 12 22 55 66 99 
aaa@qq.com://990487026.blog.51cto.com~/sort$

冒泡排序(增强版):相邻元素比较

aaa@qq.com://990487026.blog.51cto.com~/sort$ cat main.c 
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

void printfArray03(int array[], int len)
{
	int i = 0;

	for(i=0; i<len; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
}

void swap03(int array[], int i, int j)
{
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

void BubbleSort(int array[], int len) // O^2
{
	int i = 0;
	int j = 0;
	int exchange = 1; //表明数组是否已经排好序 已经排好序为0   1表示没有排好序
	for(i=0; (i<len) && exchange; i++)//只要完全排好了,就直接跳出来
	{
		exchange = 0;//认为已经排序完毕的标签，如果在内部没有改变状态则认为已经排序完成。
		for(j=len-1; j>i; j--)
		{
			if( array[j] < array[j-1] )
			{
				swap03(array, j, j-1);
				exchange = 1;//
			}
		}
	}
}

int main()
{
	int array[] ={8,3,6,1,222,4,778,963,12,45,7,8};
	int len = sizeof(array) / sizeof(*array); 
	printfArray03(array, len);
	BubbleSort(array, len);
	printfArray03(array, len);
	return 0;
}
aaa@qq.com://990487026.blog.51cto.com~/sort$ gcc main.c -Wall && ./a.out 
8 3 6 1 222 4 778 963 12 45 7 8 
1 3 4 6 7 8 8 12 45 222 778 963 
aaa@qq.com://990487026.blog.51cto.com~/sort$

希尔排序(分组技术)


aaa@qq.com://990487026.blog.51cto.com~/sort$ cat main.c 
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

void println(int array[], int len)
{
	int i = 0;

	for(i=0; i<len; i++)
	{
		printf("%d ", array[i]);
	}

	printf("\n");
}
void swap(int array[], int i, int j)
{
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

void InertionSort_ddddd(int array[], int len) // O(n*n)
{
	int i = 0;
	int j = 0;
	int k = -1;
	int temp = -1;

	//{12, 5, 433, 253, 216, 7};
	for(i=1; i<len; i++)
	{
		k = i; //待插入位置
		temp = array[k];

		for(j=i-1; (j>=0) && (array[j]>temp); j--)
		{ 
			array[j+1] = array[j]; //元素后移
			k = j; //k需要插入的位置
		}

		array[k] = temp;//元素插入
	}
}

//nlogn
void ShellSort(int array[], int len) //
{
	int i = 0;
	int j = 0;
	int k = -1;
	int temp = -1;
	int gap = len;
	do
	{
		 //业界统一实验的 平均最好情况 经过若干次后，收敛为1
		gap = gap / 3 + 1; //gap /2345 2000 都行  //O（n 1.3）
	
		for(i=gap; i<len; i+=gap)
		{
			k = i;
			temp = array[k];

			for(j=i-gap; (j>=0) && (array[j]>temp); j-=gap)
			{
				array[j+gap] = array[j];
				k = j;
			}

			array[k] = temp;
		}

	}while( gap > 1 );

}


int main()
{
	int array[] = {12, 5, 433, 253, 216, 7,12,4,6,76,88,12,13,4,6};
	int len = sizeof(array) / sizeof(*array); 

	println(array, len);
	ShellSort(array, len);
	println(array, len); 
	return 0;
}

aaa@qq.com://990487026.blog.51cto.com~/sort$ gcc main.c -Wall && ./a.out 
12 5 433 253 216 7 12 4 6 76 88 12 13 4 6 
4 4 5 6 6 7 12 12 12 13 76 88 216 253 433 
aaa@qq.com://990487026.blog.51cto.com~/sort$

快速排序(递归)


aaa@qq.com://990487026.blog.51cto.com~/sort$ cat main.c 
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
void printArray(int array[], int len)
{
	int i = 0;

	for(i=0; i<len; i++)
	{
		printf("%d ", array[i]);
	}

	printf("\n");
}

void swap5(int array[], int i, int j)
{
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}
//划分过程 第一个元素当枢轴，分成2个有效子序列
int partition(int array[], int low, int high)
{
	int pv = array[low];

	while( low < high )
	{
		while( (low < high) && (array[high] >= pv) )
		{
			high--; //比基准大，本来就在右边，所以high前移动
		}
		swap5(array, low, high);
		while( (low < high) && (array[low] <= pv) )
		{
			low++;
		}
		swap5(array, low, high);
	}
	//返回枢轴的位置。。。重要
	return low;
}

//让n个元素 依此减少 减少到1个元素的时候，因为1个元素可以看成一个有序的序列

void QSort2(int array[], int low, int high)
{
	if( low < high )
	{
		int pivot = partition(array, low, high);
		
		//对子序列1排序
		QSort2(array, low, pivot-1);
		//对子序列2排序
		QSort2(array, pivot+1, high);
	}
}

void QSort(int array[], int low, int high)
{
	if( low < high )
	{
		int pivot = partition(array, low, high);

		//对子序列1排序
		QSort2(array, low, pivot-1);
		//对子序列2排序
		QSort2(array, pivot+1, high);
	}
}

void QuickSort(int array[], int len) // O(n*logn)
{
	QSort(array, 0, len-1);
}

int main()
{
	int array[] = {12, 5, 433, 253, 216, 7};
	//int array[] = {12, 5};
	int len = sizeof(array) / sizeof(*array); 
	printArray(array, len);
	QuickSort(array, len);
	printArray(array, len);
	return 0;
}

aaa@qq.com://990487026.blog.51cto.com~/sort$ gcc main.c -Wall && ./a.out 
12 5 433 253 216 7 
5 7 12 216 253 433 
aaa@qq.com://990487026.blog.51cto.com~/sort$

归并排序:


aaa@qq.com://990487026.blog.51cto.com~/sort$ cat main.c 
#include <stdio.h>
#include <malloc.h>

void printArray06(int array[], int len)
{
	int i = 0;
	for(i=0; i<len; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
}

void swap6(int array[], int i, int j)
{
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

void Merge(int src[], int des[], int low, int mid, int high)
{
	int i = low;
	int j = mid + 1;
	int k = low;

	while( (i <= mid) && (j <= high) ) //将小的放到目的地中
	{
		if( src[i] < src[j] )
		{
			des[k++] = src[i++];
		}
		else
		{
			des[k++] = src[j++];
		}
	}

	while( i <= mid )  //若还剩几个尾部元素
	{
		des[k++] = src[i++];
	}

	while( j <= high ) //若还剩几个尾部元素
	{
		des[k++] = src[j++];
	}
}

//每次分为两路 当只剩下一个元素时，就不需要在划分
void MSort(int src[], int des[], int low, int high, int max)
{
	if( low == high ) //只有一个元素，不需要归并，结果赋给des[low]
	{
		des[low] = src[low]; 
	}
	else //如果多个元素，进行两路划分
	{
		int mid = (low + high) / 2;
		int* space = (int*)malloc(sizeof(int) * max);

		//递归进行两路，两路的划分 
		//当剩下一个元素的时，递归划分结束，然后开始merge归并操作
		if( space != NULL )
		{
			MSort(src, space, low, mid, max); 
			MSort(src, space, mid+1, high, max);
			Merge(space, des, low, mid, high); //调用归并函数进行归并
		}

		free(space);
	}
}

void MergeSort(int array[], int len) // O(n*logn)
{
	MSort(array, array, 0, len-1, len);
}

int main()
{
	
	int array[] = {21, 25, 49, 25, 16, 8};
	int len = sizeof(array) / sizeof(*array); 
	printArray06(array, len);
	MergeSort(array, len);
	printArray06(array, len);
	return 0;
}

aaa@qq.com://990487026.blog.51cto.com~/sort$ gcc main.c -Wall && ./a.out 
21 25 49 25 16 8 
8 16 21 25 25 49 
aaa@qq.com://990487026.blog.51cto.com~/sort$

【本文谢绝转载，原文来自http://990487026.blog.51cto.com】

转载于:https://blog.51cto.com/990487026/1853016

上一篇： ROS学习--第10篇：ROS机器人建模与仿真---建立移动机器人模型

下一篇：安装 docker-compose

数据结构与算法 4:排序算法,选择/插入/冒泡/希尔/快速/归并

Python实现的插入排序，冒泡排序，快速排序，选择排序算法示例

java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

Java 排序算法整合（冒泡，快速，希尔，拓扑，归并）

java 基础排序（冒泡、插入、选择、快速）算法回顾

Python实现的插入排序，冒泡排序，快速排序，选择排序算法示例

【数据结构与算法】高级排序（希尔排序、归并排序、快速排序）完整思路，并用代码封装排序函数

PHP四种排序算法实现及效率分析【冒泡排序,插入排序,选择排序和快速排序】

C语言学习历程（十七）数据结构与排序（冒泡、选择、希尔排序）算法

排序算法：冒泡排序、插入排序、选择排序、快速排序对比

JS排序算法之冒泡排序，选择排序与插入排序实例分析