您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

数据结构----各种排序方法总结

数据结构----各种排序方法总结

提示:数据结构中的排序方法包括插入排序

文章目录

    • 数据结构----各种排序方法总结
  • 一、插入排序
    • 1.直接插入排序
    • 2.折半插入排序
    • 3.希尔插入排序
  • 二、交换排序
    • 1.冒泡排序
    • 2.快速排序
  • 三、选择排序
    • 1.简单选择排序
    • 2.堆排序
  • 四、归并排序
  • 五、基数排序
  • 总结

一、插入排序

插入排序的定义:在有序序列中插入一个元素,保持序列有序,有序长度不断增加

1.直接插入排序

利用图形理清思路
在这里插入图片描述

void InsertSort(int a[], int n) {
	//在直接插入排序中,使用0号位置作为哨兵,用于暂时存放当前要插入的元素
	int i, j;
	for (i = 2; i <= n; i++) {
		//当前要插入的元素比前一个元素小时才要进行比较
		if (a[i] < a[i - 1]) {  
			a[0] = a[i];
			for (j = i - 1;a[0]<a[j]; j--) {
				a[j + 1] = a[j];  //数组的长度增加,元素后移
			}
			a[j + 1] = a[0];  //插入到正确的位置
		}
	}
 }

2.折半插入排序

折半插入排序的思想与直接插入排序的思想是差不多的,只是在查找当前要插入的元素的位置时采用了二分查找的方法,其他部分与直接插入查找一样。

void BinInsertSort(int a[], int n) {
	int low, high,mid;
	int i, j;
	//int temp;
	for (i = 2; i <= n; i++) {
	    a[0]=a[i];
		low = 1;
		high = i - 1;
		//使用二分查找的方法查找当前元素应该在有序序列中的哪一个位置
		while (low <= high) {
			mid = (low + high) / 2;
			if (a[mid] < a[0]) {
				low = mid + 1;
			}
			else {
				high = mid - 1;
			}
		}
		for (j = i-1; j > low; j--) {
			a[j + 1] = a[j];
		}
		a[low] = a[0];
	}
	for (int i = 1; i <= n; i++) {
		cout << a[i] << " ";
	}
}

3.希尔插入排序

希尔插入排序与直接插入排序的方法是一样的,不过希尔插入排序的间隔是变化的,不恒为1,下图可以帮助我们理解希尔插入排序工作的原理:
在这里插入图片描述

void ShellSort(int a[], int n, int dk) {
	int i, j;
	//代码的思路都和直接插入排序类似,只不过间隔不恒为1
	for (i = dk + 1; i <= n; i++) {
		a[0] = a[i];
		if (a[i] < a[i - dk]) {
			for (j = i - dk; a[0] < a[j]; j = j - dk) {
				a[j + dk] = a[j];
			}
			a[j + dk] = a[0];
		}
	}	
}

//希尔排序
void ShellInsertSort(int a[], int n, int dlk[], int t) {
   //dlk[]数组表示增量序列,增量序列是不唯一的
	for (int i = 0; i < t; i++) {
		ShellSort(a,n, dlk[i]);
	}	
}

/*
用希尔插入排序的效率是与增量序列的取值有关的,希尔排序也是一种不稳定的排序方法。目前还没有办法获取一个最佳的增量序列,但是可以确定的是增量序列的最后一个元素必须为1,并且所有元素除了1无其他公因子
*/

二、交换排序

1.冒泡排序

//冒泡排序
void bubble_sort(int a[], int n) {
	int i, j;
	int temp;
	for (i = 1; i <= n-1; i++) {
		for (j = 0;j<= n - i-1; j++) {
			if (a[j] > a[j + 1]) {
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		cout << a[i] << " ";
	}
}

改进后的冒泡排序

//改进的冒泡排序
void BubbleSort(int a[], int n) {
	int i, j;
	int temp;
	int flag = 1;  //作为是否有交换的标志
	for (i = 1; i <= n - 1 && flag==1; i++) {
		flag = 0;
		for (j = 0; j <= n - i - 1; j++) {
			if (a[j] > a[j + 1]) {
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
				flag = 1;   //若发生交换,那么下一趟就要比较;若本趟没有发生交换,则说明数组已经排好了
			}
		}
	}
	for (i = 0; i < n; i++) {
		cout << a[i] << " ";
	}
}

2.快速排序

快速排序不适合有序或者基本有序的序列,序列越乱,那么排序的效率越高。

//快速排序
int Partition(int a[], int n, int low, int high) {
	a[0] = a[low];
	while (low < high) {
		while (low<high && a[high]>=a[0]) {
			high--;
		}
		a[low] = a[high];
		while (low < high && a[low] <= a[0]) {
			low++;
		}
		a[high] = a[low];
	}
	a[low] = a[0];
	return low;
}

void  QuickSort(int a[], int n, int low, int high) {
	if (low >= high) {
		return;
	}
	int mid = Partition(a, n, low, high);
	QuickSort(a, n, low, mid - 1);
	QuickSort(a, n, mid + 1, high);

}

三、选择排序

1.简单选择排序

图解!
在这里插入图片描述
在这里插入图片描述

void SelectSort(int a[], int n) {
	int k;
	int x;
	for (int i = 0; i < n-1; i++) {
		k = i;
		for (int j = i+1; j < n; j++) {
			if (a[j] < a[k]) {
				k = j;
			}
		}
		//如果k==i的话就不需要进行交换了
		if (k != i) {
			x = a[i];
			a[i] = a[k];
			a[k] = x;
		}
	}
	for (int i = 0; i < n; i++) {
		cout << a[i] << " ";
	}
}

2.堆排序

堆排序的解题思路:若输出堆顶的最小值(最大值)后,是的剩余的n-1个元素的序列重新建成一个堆,则得到n个元素的次小值(次大值)........如此反复,便能得到一个有序序列,这个过程称之为堆排序。

但是,实现堆排序需要解决两个问题,分别是:
1.如何有一个无序序列建成一个堆?
2.如何在输出堆顶元素后,调整剩余元素为一个新的堆?
下面将逐一解决这两个问题,首先先解决第二个问题,因为第二个问题就相当于第一个问题的子问题
/*
* 如何在输出堆顶元素后,调整剩余元素为一个新的堆?
* 1.输出堆顶之后,以堆中最后一个元素替代
* 2.然后将根结点的值与左右子树的根结点值进行比较,并与其中的大者进行交换;
* 3.重复上述操作,直至叶子结点,将得到新的堆,称这个从堆顶至叶子的调整过程为“筛选”
*/

//将R[s]调整为大根堆
void HeapAdjust(int R[], int s, int m) {
	int rc = R[s];
	//下标从1开始,如果下标从0开始的话,那么j要从2*s+1开始
	for (int j = 2 * s; j <= m; j *= 2) {
		if (R[j] < R[j + 1]) {   //选择左子树与右子树中较小的一个,然后沿着一条路径向下寻找
			j++;
		}
		if (R[j] < rc) {     //如果找到比根结点的值要小的,则停止查找
			break;
		}
		R[s] = R[j];   //否则需要一直查找
		s = j;
	}
	R[s] = rc;   //找到位置后,将此位置的值赋值为根节点的值
}
//如何由一个无序序列建成一个堆?
//下面的例子是建立一个大根堆
void Heap(int R[],int n) {
	//只调整不是叶子结点的结点
	for (int i = n / 2; i >= 1; i--) {
		HeapAdjust(R, i, n);
	}
}
//堆排序
void HeapSort(int R[], int n) {
	//下标从1开始
	int i;
	int  temp;

	//先建立一个最大堆
	for (i = n / 2; i >= 1; i--) {
		HeapAdjust(R, i, n);
	}
    //每次都使用最后一个结点替代输出堆顶元素后的根结点
	for (i = n; i > 1; i--) {
		temp = R[i];
		R[i] = R[1];
		R[1] = temp;
		//替代后需要重新调整堆
		HeapAdjust(R, 1, i - 1);
	}
}

四、归并排序

图解:
在这里插入图片描述

//归并排序
void Merge(int  *a, int start, int mid, int end) {
	int i, j,k=0;
	int* c = new int[end-start+1];
	//a = new int[end - start + 1];
	i = start;
	j = mid + 1;
	while (i <= mid && j <= end) {
		if (a[i] < a[j]) {
			c[k++] = a[i++];
		}
		else {
			c[k++] = a[j++];
		}
	}
	while (i <= mid) {
		c[k++] = a[i++];
	}
	while (j <= end) {
		c[k++] = a[j++];
	}

	for (int s = 0; s < k; s++) {
		a[start + s] = c[s];
	}
	delete[] c;
}
void MergeSort(int a[],int n,int start, int end) {
	if (start >= end) {
		return;
	}
	int mid = (start + end) / 2;

	//下面两个递归是为了将数组进行划分,然后从下往上进行排序
	MergeSort(a, n, start, mid);
	MergeSort(a, n, mid + 1, end);

	Merge(a, start, mid, end);

}


五、基数排序

图解

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

总结

提示:各种排序方法比较
在这里插入图片描述


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进