微网站一键导航,wordpress 左边栏,网络营销网站建设的角度,启用中文域名大网站#x1f47b;内容专栏#xff1a; 《数据结构与算法篇》 #x1f428;本文概括#xff1a;常见交换排序包括冒泡排序与快速排序#xff0c;本篇讲述冒泡排序与快速排序的思想及实现、复杂度分析。 #x1f43c;本文作者#xff1a; 花 蝶 #x1f438;发布时间#… 内容专栏 《数据结构与算法篇》 本文概括常见交换排序包括冒泡排序与快速排序本篇讲述冒泡排序与快速排序的思想及实现、复杂度分析。 本文作者 花 蝶 发布时间2023.8.27 一、冒泡排序
基本思想 冒泡排序Bubble Sort是一种简单的排序算法其基本思想是通过两两交换相邻元素的位置使得较大或较小的元素逐步“冒泡”到数组的一端顶部或底部重复“冒泡”的过程直到序列没有要交换的元素为止从而实现排序。 算法步骤 1、 从数组的起始位置开始依次比较相邻的两个元素。如果相邻元素的顺序错误前者大于后者或者前者小于后者取决于是升序还是降序排序则交换这两个元素的位置 2、继续进行相邻元素的比较和交换直到遍历到数组的末尾。这样一轮下来最大或最小的元素就会“冒泡”到数组的一端。 3、重复上述步骤但不再考虑已经排序好的末尾部分。每一轮操作都会将一个最大或最小的元素移到正确的位置。 4、 经过多轮的比较和交换最终整个数组会变得有序。如果在某一轮没有进行任何交换操作时说明数组已经有序可以直接跳出循环。 动图演示 代码实现
//冒泡排序
//时间复杂度O(N^2)
void BubbleSort(int* a, int n)
{//控制冒泡排序的趟数for(int i 0; i n - 1; i){//假设数组有序int flag 1;//控制每趟的过程for (int j 0; j n - 1 - i; j){if (a[j] a[j 1]){Swap(a[j], a[j 1]);flag 0;}}//说明没有发生交换数组已经有序跳出循环即可if (flag 1) break;}
}冒泡排序的特性 冒泡排序的核心思想就是通过反复比较相邻元素并交换它们的位置从而逐步将最大或最小的元素移动到合适的位置。尽管冒泡排序的时间复杂度较高平均和最坏情况下都是 O(N^2)可以看作是一个等差数列的求和)但它的实现相对简单适用于小规模的数据集因此具有较强的教学意义想必大家在刚开始学习编程时学的一个排序就是冒泡排序吧哈哈。 二、快速排序递归版本
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
//快排(递归版本)
void QuickSort(int* a, int begin, int end)
{if (begin end) return;int keyi Partition(a, begin, end); //前序遍历//递归基准值左边的区间QuickSort(a, begin, keyi - 1);//递归基准值右边的区间QuickSort(a, keyi 1, end);
}上述为快速排序递归实现的主框架发现与二叉树前序遍历规则非常像大家在写递归框架时可想想二叉树前序遍历规则即可快速写出来后续只需分析如何按照基准值来对区间中数据进行划分的方式即可。 下面用三个版本实现hoare版本、挖坑法、前后指针法
1.hoare版本 1、选择基准元素key通常是数组中的第一个元素。 2、使用两个指针L和R一个指向数组的开头较小值的区域一个指向数组的末尾较大值的区域。 3、交换的目标是L找到比基准大的元素R找到比基准小的元素。不断交换指针所指的元素直到两个指针相遇。 4、当两个指针相遇时交换基准元素与当前相遇位置的元素此时数组被划分为左右两个子数组。 5、对左右两个子数组递归地应用相同的分区步骤直到所有子数组都有序 算法分析
①原始序列 ②right向前移动找比key小的位置left往后移动找比key大的位置然后交换。 ③继续往后寻找直到两个指针相遇。 ④交换基准元素与当前相遇位置的元素。 ⑤这样子我们发现基准值左边的区间里面的元素都比基准值小右边的区间里面的元素都比基准值大。我们可以按照前序遍历的思想对左边区间进行递归操作右边区间也进行递归操作。
代码实现
//hoare版本
int Partition1(int* a, int left, int right)
{int keyi left;while (left right){//注意 要加上left right 否则会出现越界//若不判断等于基准值也会出现死循环的情况//右边找小while (left right a[right] a[keyi]){right--;}//左边找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);return left;
}//快排(递归版本)
void QuickSort(int* a, int begin, int end)
{//当区间不存在或者只剩一个元素就回溯if (begin end) return;int keyi Partition1(a, begin, end);//前序遍历//递归基准值左边的区间QuickSort(a, begin, keyi - 1);//递归基准值右边的区间QuickSort(a, keyi 1, end);
}2.挖坑法 挖坑法的基本思想是 1、首先选择一个基准元素通常是数组中的第一个元素作为“坑”(hole)。前提需要将这个基准元素用一个临时变量key存起来。2、将基准元素挖出形成一个空位坑。3、从数组的另一端开始从右向左遍历找到一个比基准元素小的元素然后将这个元素填入之前的坑中。4、继续从左向右遍历找到一个比基准元素大的元素然后将这个元素填入上一步的坑中。5、重复执行步骤 3 和步骤 4直到左右指针相遇。6、此时基准元素的位置就是这个相遇的位置将基准元素填入这个坑中。 算法分析
①原始序列 ②将基准值存放到临时变量key中形成一个坑位。 ③从右向左遍历R找到比基准值小的元素将这个元素填入到之前的坑中此时当前位置就形成了新坑。 ④紧接着从左往右遍历L寻找比基准值大的元素将这个元素填入到上一步的坑中此时当前位置形成了新坑。 ⑤重复以上步骤后直到左右指针相遇最后会形成一个坑将临时变量放入坑中。 ⑥这样子我们发现基准值左边的区间里面的元素都比基准值小右边的区间里面的元素都比基准值大。我们可以按照前序遍历的思想对左边区间进行递归操作右边区间也进行递归操作。
代码实现
//挖坑法
int Partition2(int* a, int left, int right)
{int key a[left];//挖坑int hole left;while (left right){//右边找小while (left right a[right] key){right--;}a[hole] a[right];hole right;//左边找大while (left right a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}
//快排(递归版本)
void QuickSort(int* a, int begin, int end)
{//当区间不存在或者只剩一个元素就回溯if (begin end) return;int keyi Partition2(a, begin, end);//前序遍历//递归基准值左边的区间QuickSort(a, begin, keyi - 1);//递归基准值右边的区间QuickSort(a, keyi 1, end);
}3.前后指针法 基本思想在快速排序的划分过程中使用前后指针法来确定基准元素的位置最后将数组划分成两部分一部分小于基准元素另一部分大于基准元素。 1、首先选择一个基准元素key(通常是数组中的第一个元素)。2、使用两个指针prev指向数组的开头cur指向prev的后一个位置。3、判断cur指向的数据是否小于key。若小于则prev后移一位cur指向的内容与prev指向的内容交换然后cur4、若cur指向的数据大于key则cur重复步骤3和步骤4直到cur指针走完(最后一个元素的下一个位置)最后将key与prev指向的元素交换。 动图演示 //前后指针法
int Partition3(int* a, int left, int right)
{int prev left;int cur prev 1;int keyi left;//cur小于key交换prev与cur的位置//将大的位置翻滚时往后挪动小的位置移动前面while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[cur], a[prev]);}cur;}//将key与prev指向的元素交换。Swap(a[prev], a[keyi]);return prev;
}//快排(递归版本)
void QuickSort(int* a, int begin, int end)
{//当区间不存在或者只剩一个元素就回溯if (begin end) return;int keyi Partition3(a, begin, end);//前序遍历//递归基准值左边的区间QuickSort(a, begin, keyi - 1);//递归基准值右边的区间QuickSort(a, keyi 1, end);
}快速排序(递归版本)的特性
时间复杂度
选择基准元素影响时间复杂度若基准元素key偏向于所有元素中的中位数则时间复杂度处于较好的情况若基准元素key是所有元素中最小的或者接近最小值那么时间复杂度就处于较坏的情况。 平均情况下的时间复杂度 在平均情况下快速排序的时间复杂度为 O(n log n)。这是因为在每次分区过程中数组会被划分成大致相等的两部分。在每次递归中都会将问题的规模减半递归的展开图可以看作是一颗满二叉树所以递归的深度为 O(log n)每层递归的分区操作都需要 O(n) 的时间因此总的时间复杂度为 O(n*log n)最坏情况下的时间复杂度 在最坏情况下快速排序的时间复杂度为 O(n^2)。这种情况发生在每次划分后一个子数组为空另一个子数组包含所有的元素。这样会导致递归树变得很不平衡每次递归的问题规模只减少一个元素。虽然快速排序通常能够避免这种情况但在某些情况下例如已经有序的数组最坏情况可能出现。 解决方案 随机数选择基准元素 在每次划分时随机选择一个基准元素这可以减少最坏情况的发生概率。三数取中法 在选择基准元素时不仅考虑第一个和最后一个元素还考虑数组中间位置的元素选择其中值大小居中的元素作为基准。 这里提供一种三数取中的方法以hoare版本为例:
//三数取中返回下标
int GetMidIndex(int* a, int left, int right)
{int mid (left right) 1;if (a[left] a[mid]){if (a[mid] a[right]) return mid;else if (a[left] a[right]) return left;else return mid;}else //a[left] a[mid]{if (a[mid] a[right]) return mid;else if (a[right] a[left]) return left;else return right;}
}
//hoare版本
int Partition1(int* a, int left, int right)
{//将中位数与数组的第一个元素(基准值)进行交换int midi GetMidIndex(a, left, right);Swap(a[left], a[midi]);int keyi left;while (left right){//右边找小while (left right a[right] a[keyi]){right--;}//左边找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);return left;
}后面会更新快排的非递归版本……可到数据结构专栏查看 更多数据结构与算法系列文章 【传送门】
