数据结构~19.选择类排序

本文是上一篇文章的后续,详情点击该链接~

简单选择排序

基本概念

       顾名思义,选择类排序主要操作就是选择。简单的选择排序就采用最简单的选择方法。从头到尾的来扫描这个序列。找到最小的一个元素,和第一个元素交换,然后从剩下的元素中,继续采用这种方式。

       就举个例子,现在有一个序列,它们分别是 19,36,2,5,88,3,66,17,18。在选择排序的过程中,把整个序列都分成有序部分和无序部分。先进行第一趟排序,我们在无序序列中找到最小的一个元素,也就是2,让2和19交换位置,交换之后待交换的元素就少了一个,然后让剩下的元素继续比较。

代码实现

void SelectSort(int arr[], int n) {
	int i, j, k,temp;
	for (i = 0; i < n; i++) {
		k = i;
		//开始选择
		for (j = i + 1; j < n; j++) {
			if (arr [k] > arr[j]) {
				k = j;
			}
		}
		//让最小的元素和无序序列中第一个元素进行交换
		temp = arr[i];
		arr[i] = arr[k];
		arr[k] = temp;
	}
}

算法复杂度

时间复杂度

       两层循环的执行次数和初始序列没有关系,外层循环执行n次,内层循环执行n-1次,而最内层循环中的比较操作是最主要的操作。这个执行的次数就是( n-1+1 )( n-1 ) / 2 = n( n-1 ) / 2。因此算法复杂度为 O ( n² )

空间复杂度

       这个算法所用到的辅助空间不会随着规模的变化而变化,是固定的。所以说空间复杂度应该是 O ( 1 )

堆排序

基本概念

       堆是一种数据结构,其实也可以把它看成一颗完全二叉树。而这个完全二叉树呢,它是任何一个非叶结点的值都不大于(或者说不小于)其左右孩子结点的值。若父亲大孩子小,那么这个堆就叫做大顶堆,如果父亲小,孩子大,那么就叫做小顶堆。根据刚刚我们对堆的定义就会知道,代表堆的这颗完全二叉树的根节点的值是最大(或者最小)的,所以我们将一个无序序列调整成一个堆,就可以找到这个序列的最大值(或最小值),然后将找出的这个值交换到序列的最后或者最前实现排序。

代码实现

//这个函数完成在数组arr[left]到arr[right]的范围内堆在位置left上的结点进行调整
void function(int arr[],int left,int right) {
	//arr[j] 是 arr[i]的左孩子结点
	int i = left, j = 2 * i;
	int temp = arr[i];
	while (j < right) {
		//若右孩子较大,则把j指向右孩子
		if (j < right && arr[j] < arr[j + 1]) {
			//j变为 2 * i + 1
			j++;
		}
		if (temp < arr[j]) {
			//把arr[j] 调整到双亲结点的位置上
			arr[i] = arr[j];
			//修改 i 和 j 的值,以便继续向下调整
			i = j;
			j = i * 2;
		}
		else {
			//调整结束
			break;
		}
	}
	//将调整结点的值放入到最终位置
	arr[i] = temp;
}
//堆排序函数
void heapSort(int arr[],int n) {
	int i, temp;
	//建立初始堆
	for (i = n / 2; i >= 1; i--) {
		function(arr,i,n);
	}
	//进行 n - 1 次循环,完成堆排序
	for (i = n; i >= 2; i--) {
		temp = arr[1];
		arr[1] = arr[i];
		arr[i] = temp;
		function(arr,1,i - 1);
	}
}

算法复杂度

时间复杂度分析

       对于function函数里面的j其实是走了一条从当前结点到叶子结点的路径。而完全二叉树的高度是 log 2 ( n + 1 ),那么对每个结点调整的时间复杂度就是 O ( log 2 n )。

       而排序的那个函数,它的基本操作总次数就是两个for循环的基本操作次数之和,第一次循环的次数是O ( log 2 n ) * n / 2,而第二个循环呢,它的基本操作次数是O ( log 2 n ) * ( n - 1 )。 所以说， 整个算法的基本操作是 O ( log 2 n ) * n / 2 + O ( log 2 n ) * ( n - 1 )。我们把它化简之后就是 O( nlog2n )。

空间复杂度分析

       这个算法所需要的空间复杂度一般情况下是不会变化的,所以是 O ( 1 )