排序算法1:冒泡排序、快速排序、插入排序

这篇具有很好参考价值的文章主要介绍了排序算法1:冒泡排序、快速排序、插入排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

排序算法:交换类排序,插入类排序、选择类排序、归并类排序

交换类排序:冒泡排序、快速排序

一、冒泡排序

排序算法1:冒泡排序、快速排序、插入排序,C语言,排序算法,算法,数据结构

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int ElemType;
typedef struct{
	ElemType *elem; //整形指针,申请的堆空间的起始地址存入elem 
	int TableLen; //存储动态数组里边元素的个数 
}SSTable;
 
void ST_Init(SSTable &ST,int len){
	ST.TableLen=len;
	ST.elem=(ElemType *)malloc(sizeof(ElemType)*ST.TableLen);
	int i;
	srand(time(NULL)); //随机数生成
	for(i=0;i<ST.TableLen;i++){
		ST.elem[i]=rand()%100;
	} 
}
 
void ST_print(SSTable ST){
	int i;
	for(i=0;i<ST.TableLen;i++){
		printf("%3d",ST.elem[i]);
	}
	printf("\n");
}

void swap(ElemType &a,ElemType &b){
	ElemType tmp;
	tmp=a;
	a=b;
	b=tmp;
} 

//两层循环 
//优先写内层循环,再写外层循环 
void BubbleSort(ElemType A[],int n){
	int i,j;
	bool flag; 
	for(i=0;i<n-1;i++){ //控制的是有序数的数目
	    flag=false; 
		for(j=n-1;j>i;j--){ //内层控制比较和交换 
			if(A[j-1]>A[j]){
				swap(A[j-1],A[j]);
				flag=true;
			}
		}
		if(flag==false){ //如果一趟没有发生任何交换,说明数组有序,提前结束排序
		    return; 
		}
	} 	
}
 
int main(){
	SSTable ST;
	ST_Init(ST,10); 
	ST_print(ST);
	BubbleSort(ST.elem,10); 
	ST_print(ST);
	return 0;
}

 时间复杂度:内层是j>i,外层是从0到n-1,运行的总次数是1+2+3+4+...+n-1,即O()

空间复杂度:O(1),没有使用额外空间,不会因为n的变化而变化

如果数组本身有序,最好的时间复杂度是O(n)

二、快速排序

核心:分治思想

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int ElemType;
typedef struct{
	ElemType *elem; //整形指针,申请的堆空间的起始地址存入elem 
	int TableLen; //存储动态数组里边元素的个数 
}SSTable;
 
void ST_Init(SSTable &ST,int len){
	ST.TableLen=len;
	ST.elem=(ElemType *)malloc(sizeof(ElemType)*ST.TableLen);
	int i;
	srand(time(NULL)); //随机数生成
	for(i=0;i<ST.TableLen;i++){
		ST.elem[i]=rand()%100;
	} 
}
 
void ST_print(SSTable ST){
	int i;
	for(i=0;i<ST.TableLen;i++){
		printf("%3d",ST.elem[i]);
	}
	printf("\n");
}

void swap(ElemType &a,ElemType &b){
	ElemType tmp;
	tmp=a;
	a=b;
	b=tmp;
} 

int Partition(ElemType A[],int low,int high){
	ElemType pivot=A[low]; //拿最左边的作为分割值,并存储下来 
	while(low<high){
		while(low<high&&A[high]>=pivot){ //从后往前遍历,找到一个比分割值小的 
			--high;
		}
		A[low]=A[high]; 
		while(low<high&&A[low]<=pivot){
			++low;
		}
		A[high]=A[low];
	}
	A[low]=pivot;
	return low; //返回分割值所在的下标 
}

//递归实现
void QuickSort(ElemType A[],int low,int high){
	if(low<high){
		int pivotpos=Partition(A,low,high);
		QuickSort(A,low,pivotpos-1);
		QuickSort(A,pivotpos+1,high);
	}
} 
 
int main(){
	SSTable ST;
	ST_Init(ST,10); 
	ST_print(ST);
	QuickSort(ST.elem,0,9); 
	ST_print(ST);
	return 0;
}

排序算法1:冒泡排序、快速排序、插入排序,C语言,排序算法,算法,数据结构空间复杂度与n有关 

三、插入排序

插入排序:直接插入排序、折半插入排序、希尔排序

直接插入排序

排序算法1:冒泡排序、快速排序、插入排序,C语言,排序算法,算法,数据结构

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int ElemType;
typedef struct{
	ElemType *elem; //整形指针,申请的堆空间的起始地址存入elem 
	int TableLen; //存储动态数组里边元素的个数 
}SSTable;
 
void ST_Init(SSTable &ST,int len){
	ST.TableLen=len;
	ST.elem=(ElemType *)malloc(sizeof(ElemType)*ST.TableLen);
	int i;
	srand(time(NULL)); //随机数生成
	for(i=0;i<ST.TableLen;i++){
		ST.elem[i]=rand()%100;
	} 
}
 
void ST_print(SSTable ST){
	int i;
	for(i=0;i<ST.TableLen;i++){
		printf("%3d",ST.elem[i]);
	}
	printf("\n");
}

void InsertSort(ElemType *arr,int n){
	int i,j,insertVal;
	for(i=1;i<n;i++){ //控制要插入的数 
		insertVal=arr[i]; //先保存要插入的值
		//内层控制比较,往后覆盖 
		for(j=i-1;j>=0&&arr[j]>insertVal;j--){
			arr[j+1]=arr[j];
		} 
		arr[j+1]=insertVal;
	}
}
 
int main(){
	SSTable ST;
	ST_Init(ST,10); 
	ST_print(ST);
	InsertSort(ST.elem,10); 
	ST_print(ST);
	return 0;
}

排序算法1:冒泡排序、快速排序、插入排序,C语言,排序算法,算法,数据结构文章来源地址https://www.toymoban.com/news/detail-834419.html

到了这里,关于排序算法1:冒泡排序、快速排序、插入排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包