1、冒泡排序
//冒泡排序 void BubbleSort(int* nums, int len) { for (int i = 1; i < len; i++) { for (int j = 1; j < len - i + 1; j++) { if (nums[j] < nums[j - 1]) swap(nums[j], nums[j - 1]); } } }
2、快速排序
//快速排序 void quickSort(int arr[], int left, int right) { int left = left; int right = right; int temp = 0; if (left < right) { //待排序的第一个元素作为基准元素 temp = arr[left]; //从左右两边交替扫描，直到left = right while (left != right) { //从右往左扫描，找到第一个比基准元素小的元素 while (right > left && arr[right] >= temp) right--; arr[left] = arr[right]; //找到这种元素arr[right]后与arr[left]交换 //从左往右扫描，找到第一个比基准元素大的元素 while (left < right && arr[left] <= temp) left++; arr[right] = arr[left]; //找到这种元素arr[left]后，与arr[right]交换 } arr[right] = temp; //基准元素归位 quickSort(arr, left, left - 1); //对基准元素左边的元素进行递归排序 quickSort(arr, right + 1, right); //对基准元素右边的进行递归排序 } }
3、插入排序
//插入排序 void insertSort(int* nums, int len) { for (int i = 0; i < len; i++) { for (int j = i ; j > 0; j--) { if (nums[j] < nums[j - 1]) swap(nums[j], nums[j - 1]); } } }
4、选择排序
//选择排序 void slectSort(int* nums, int len) { int mid = 0; for (int i = 0; i < len - 1; i++) { mid = i; for (int j = i + 1; j < len; j++) { if (nums[j] < nums[mid]) mid = j; } swap(nums[mid], nums[i]); } }
5、桶排序
//桶排序 vector<int> bucketSort(vector<int>& nums) { int len = nums.size(); if (len == 0) return {}; //获取最大值及最小值 int mins = *min_element(nums.begin(), nums.end()); int maxs = *max_element(nums.begin(), nums.end()); //初始化桶的个数 k=log(len)，也可以随机初始化 int n = 5; //初始化桶 vector<vector<int>> res(5); int d = maxs - mins; //把所有元素放到各自桶中 for (int i = 0; i < len; i++) { //计算元素所对应的桶的序号 int index = (nums[i] - mins) * n / d; //下标索引从0开始 if (index == n) index--; res[index].push_back(nums[i]); } for (int i = 0; i < n; i++) { sort(res[i].begin(), res[i].end()); } vector<int> v; for (int i = 0; i < n; i++) { for (int j = 0; j < res[i].size(); j++) v.push_back(res[i][j]); } return v; }
6、堆排序
#include <stdio.h> void Swap(int *heap, int len); /* 交换根节点和数组末尾元素的值 */ void BuildMaxHeap(int *heap, int len);/* 构建大顶堆 */ int main() { int a[6] = {7, 3, 8, 5, 1, 2}; int len = 6; /* 数组长度 */ int i; for (i = len; i > 0; i--) { BuildMaxHeap(a, i); Swap(a, i); } for (i = 0; i < len; i++) { printf("%d ", a[i]); } return 0; } //堆排序，大顶堆，构建大顶堆 void BuildMaxHeap(int* heap, int len) { //最后一个非叶子节点为：len / 2 - 1 for (int i = len / 2 - 1; i >= 0; i--) { //判断左子树是否满足大顶堆关系 if (2 * i + 1 < len && heap[i] < heap[2 * i + 1]) { int tem = heap[i]; heap[i] = heap[2 * i + 1]; heap[2 * i + 1] = tem; //交换之后要判断左子树与左子树的子树是否也满足该关系 if ((2 * (2 * i + 1) + 1 < len && heap[2 * i + 1] < heap[2 * (2 * i + 1) + 1] )|| (2 * (2 * i + 1) + 2 < len && heap[2 * i + 1] < heap[2 * (2 * i + 1) + 2])) { BuildMaxHeap(heap, len); } } //判断右子树是否满足大顶堆关系 if (2 * i + 2 < len && heap[i] < heap[2 * i + 2]) { int tem = heap[i]; heap[i] = heap[2 * i + 2]; heap[2 * i + 2] = tem; //交换之后要判断右子树与右子树的子树是否也满足该关系 if ((2 * (2 * i + 2) + 1 < len && heap[2 * i + 2] < heap[2 * (2 * i + 2) + 1]) || (2 * (2 * i + 2) + 2 < len && heap[2 * i + 2] < heap[2 * (2 * i + 2) + 2])) { BuildMaxHeap(heap, len); } } } } /* Function: 交换交换根节点和数组末尾元素的值*/ void Swap(int *heap, int len) { int temp; temp = heap[0]; heap[0] = heap[len-1]; heap[len-1] = temp; }
7、归并排序
void Merg(int* nums, int left, int right) { vector<int> temp(10); int mid = left + (right - left) / 2; int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { if (nums[i] < nums[j]) temp[k++] = nums[i++]; else temp[k++] = nums[j++]; } while (i <= mid) temp[k++] = nums[i++]; while (j <= right) temp[k++] = nums[j++]; for (i = left, k = 0; i <= right; i++, k++) nums[i] = temp[k]; } void MergeSort(int* nums, int left, int right) { if (left < right) { int mid = left + (right - left) / 2; MergeSort(nums, left, mid); MergeSort(nums, mid + 1, right); Merg(nums, left, right); } }
