排序 (快速排序、堆排序、冒泡排序、选择排序、直接插入、希尔排序)
排序 快速 选择 冒泡排序 堆排序 希尔
2023-09-11 14:19:17 时间
//=========================================快速排序==========================================
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型vector 待排序的数组
* @return int整型vector
*/
vector<int> MySort(vector<int>& arr)
{
// write code here
mySort1(arr);
return arr;
}
void mySort1(vector<int>& arr) {
quicksort(arr, 0, arr.size() - 1);
}
void quicksort(vector<int> &arr, int left, int right) {
if (left > right)
return;
int pivotIndex = partition(arr, left, right); // 标杆值所在的位置
quicksort(arr, left, pivotIndex - 1); // 左半边
quicksort(arr, pivotIndex + 1, right); // 右半边
}
int partition(vector<int> &arr, int left, int right) {
// 最后一个值当做标杆
int counter = left; // 记录小于标杆值的个数
while (left < right) {
if (arr[left] < arr[right]) { // 当前值和标杆值比较,决定是放在左边还是右边
swap(arr[left], arr[counter]);
counter++;
}
left++;
}
swap(arr[counter], arr[right]); // 最后把标杆值移到中间位置,然后返回下标。
return counter;
}
};
//=================================================堆排序=========================================
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型vector 待排序的数组
* @return int整型vector
*/
vector<int> MySort(vector<int>& arr)
{
// write code here
heapSort(arr);
return arr;
}
void heapSort(vector<int> &arr) {
priority_queue<int, vector<int>, greater<int>> q; //小顶堆构造
for (int i = 0; i < arr.size(); i++) {
q.push(arr[i]);
}
for (int i = 0; i < arr.size(); i++) {
arr[i] = q.top();
q.pop();
}
}
};
//==================================冒泡排序=====================================
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型vector 待排序的数组
* @return int整型vector
*/
vector<int> MySort(vector<int>& arr)
{
// write code here
bubblesort(arr);
return arr;
}
void bubblesort(vector<int> &arr) {
for (int i = 0; i < arr.size(); i++)
{
for (int j = i + 1; j < arr.size(); j++)
{
if (arr[j] < arr[i])
{
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
}
};
//================================================选择排序===================================
void selectsort(vector<int> &arr) {
for (int i = 0; i < arr.size(); i++)
{
int index = i; // 需要定义index
for (int j = i + 1; j < arr.size(); j++)
{
if (arr[j] < arr[index]) // 比较的不再是 i 和 j 。
{
index = j;
}
}
swap(arr[i], arr[index]); // for 内部实现 i 和 index 的交换
}
}
//=============================================直接插入========================================
void insetionSort(vector<int>& arr) {
int preIndex = 0;
int currentVal = 0;
for (int i = 1; i < arr.size(); i++) {
preIndex = i - 1;
currentVal = arr[i];
while (arr[preIndex] > currentVal) {
arr[preIndex + 1] = arr[preIndex];
preIndex--; //不知道为啥要 --
}
arr[preIndex + 1] = currentVal; //for 里面 ++ 后赋值
}
}
//==========================================希尔排序===========================================
void xierSort(vector<int>& arr) {
for (int gap = arr.size() / 2; gap > 0; gap /= 2)
{
for (int i = gap; i < arr.size(); i++)
{
int j = i;
while (j - gap >= 0 && arr[j] < arr[j - gap])
{
swap(arr[j], arr[j - gap]);
j -= gap;
}
}
}
}
相关文章
- 排序算法(选择、冒泡、插入、快速、希尔、归并、堆排序)
- 手机便签设置按数字序号排序教程?
- mysql 必知必会整理—sql 排序与过滤[三]
- 算法常识——快速排序
- Java快速排序的调试
- 【堆排序】十大排序算法之堆排序
- 从零开始_学_数据结构(六)——排序(冒泡、插入、希尔、简单选择、归并、快速)
- 【华为OD机试】1022 - 字符串排序
- LCS 02. 完成一半题目-统计重复元素+快速排序
- 2171. 拿出最少数目的魔法豆-快速排序+前缀和
- 面试题 08.08. 有重复字符串的排列组合-快速排序+回溯深度优先搜索
- 1528. 重新排列字符串-自定义快速排序
- 781. 森林中的兔子-快速排序加贪心算法
- Python数据分析与展示:pandas库的数据排序-12
- 387集Go语言核心编程培训视频教材整理 | 排序和查找
- 归并排序学习
- 785. 快速排序(模板)