文章目录
- 直接插入排序
- 希尔排序
- 冒泡排序
- 快速排序
- 选择排序
- 堆排序
- 归并排序
- 桶排序
直接插入排序
vector<int> insertSort(vector<int> num)
{
int i, j, temp;
for (i = 1; i < num.size(); i++)
{
temp = num[i];
for (j = i - 1; j >= 0 && temp<num[j]; j--)//易错点，&&前后不可拆分为if语句，这是一个连续的循环
{
num[j + 1] = num[j];
}
num[j + 1] = temp;
}
return num;
}
希尔排序
vector<int> shellSort(vector<int> num)
{
int i, j, temp;
int n = num.size();
for (int gap = n / 2; gap > 0; gap = gap / 2)//增量设置的边界条件不能等于0
{
for (i = gap; i < n; i++)
{
temp = num[i];
for (j = i - gap; j >= 0 && temp<num[j]; j -= gap)
num[j + gap] = num[j];
num[j + gap] = temp;
}
}
return num;
}
冒泡排序
vector<int> bubbleSort(vector<int> num)
{
int n = num.size();
for (int i = 0; i < n; i++)
{
bool flag = false;
for (int j = 0; j < n - i - 1; j++)
{
if (num[j + 1] < num[j])
{
swap(num[j], num[j + 1]);
flag = true;
}
}
if (!flag)
break;
}
return num;
}
快速排序
int paratition(vector<int>& num, int low, int high)
{
int base = num[low];//选择基准元素
while (low < high)
{
//num[high] >= base中的=判断不能省略
while (num[high] >= base && low < high ) high--;//该循环跳出语句中&&前后衔接可互换，但由于&&的短路特性，更建议先判断low<high
num[low] = num[high];
while (low < high && num[low] <= base ) low++;
num[high] = num[low];
}
num[low] = base;
return low;
}
void quickSort(vector<int>& num,int low,int high)
{
if (low < high)//该语句不可少，只有在low<high时的交换才起作用，否则在递归时会出现错误
{
int j = paratition(num, low, high);
quickSort(num, low, j - 1);
quickSort(num, j + 1, high);
}
}
选择排序
vector<int> selectSort(vector<int> num)
{
int n = num.size();
for (int i = 0; i < n; i++)
{
int min = i;
for (int j = i + 1; j < n; j++)
{
if (num[j] < num[min])
{
min = j;
}
}
if (min != i)
{
swap(num[min], num[i]);
}
}
return num;
}
堆排序
void heapAdjust(vector<int>& num, int p, int n)
{
int temp = num[p];//取出根节点，待找到该根节点的子树中最大的节点之后与该根节点进行交换
for (int i = 2 * p + 1; i < n; i = 2*i+1)//遍历子树，寻找最大节点
{
if (i + 1 < n && num[i + 1] > num[i]) i++;//首先比较父节点的两个孩子的最大值
if (temp >= num[i]) break;//如果父节点比两个孩子节点都大，则不需要交换，说明当前子树已经是大根堆
num[p] = num[i];//将最大孩子进行上移为父节点
p = i;//继续遍历子树，保证其子树也是大根堆
}
num[p] = temp;
}
void heapSort(vector<int>& num)
{
//构建初始大根堆
int n = num.size();
for (int i = n / 2 - 1; i >= 0; i--)//从最后一个非叶子节点向上构造大根堆
heapAdjust(num, i, n);
for (int j = n - 1; j >= 0; j--)
{
//大根堆的第一个数字是最大的,将大根与最后一个数字进行交换，则该数组的最后一个数一定是最大的
swap(num[0], num[j]);
//将数组长度减去1后，调整堆，重新进行交换
heapAdjust(num, 0, j);
}
}
归并排序
void merge(vector<int>& num, int low, int mid, int high)
{
vector<int> help;//定义辅助数组
help.resize(high - low + 1);
int i = low, j = mid + 1, k = 0;//i为第一序列的扫描指针，j为第二序列的扫描指针，k为辅助数组的扫描指针
while (i <= mid && j <= high)// = 不能省略
{
if (num[i] < num[j]) help[k++] = num[i++];
else help[k++] = num[j++];
}
while (i <= mid) help[k++] = num[i++];
while (j <= high) help[k++] = num[j++];
for (int i = low, k = 0; i <= high; i++, k++)
{
num[i] = help[k];
}
}
void mergeSort(vector<int>& num, int low, int high)
{
if (low == high)//递归跳出条件，即当子序列长度为1时终止递归
return;
int mid = (low + high) / 2;
mergeSort(num, low, mid);//递归划分左区间，直到区间序列个数为1时终止递归
mergeSort(num, mid + 1, high);//递归划分右区间，知道区间序列个数为1时终止递归
merge(num, low, mid, high);//合并
}
桶排序
定义一个编号为[0,max]的桶，其中max为待排序数组当中的最大值
遍历数组，将数组的中的元素值放到该元素对应编号的桶中，桶数组的值代表放入桶中的个数，初始时桶中个数为0
按照桶的编号顺序依次取出桶中的元素
//桶排序
void bucketSort(vector<int>& nums)
{
//思想：
int n = nums.size();
int max=0;
for (int i = 0; i < n; i++)
{
if (nums[i] > max)
max = nums[i];
}
vector<int> bucket(max+1, 0);//初始化桶
for (int i = 0; i < n; i++)//将数组中的数放到对应编号的桶中
bucket[nums[i]]++;
for (int i = 0,j=0; i <= max; i++)
{
while (bucket[i]--> 0)
nums[j++] = i;
}
}
