排序算法~选择类排序

╰半橙微兮° 2022-12-03 13:17 106阅读 0赞

# 选择类排序 #

## [本文是上一篇文章的后续,详情点击该链接~][Link 1] ##

## 简单选择排序 ##

### 基本概念 ###

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

就举个例子,现在有一个序列,它们分别是 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 )

[Link 1]: https://blog.csdn.net/qq_41424688/article/details/108329752