文章目录
- 直接插入排序
- 希尔排序
- 冒泡排序
- 快速排序
- 选择排序
- 堆排序
- 归并排序
- 桶排序
直接插入排序
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<highnum[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;}
}
