选择类排序

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

简单选择排序

基本概念

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

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