一.选择排序
口诀:
1.将数组分为已排序区和待排序区;
2.每一轮从已排序区和待排序中选择一个最小/最大的元素放到已排序区的左端;
3.直到待排序区没有元素为止;
void selection_sort(int* arr, int l, int r) {for (int i = l; i < r - 1; i++) {int ind = i;for (int j = i + 1; j < r; j++) {if (arr[j] < arr[ind]) ind = j;}swap(arr[i], arr[ind]);}return;
}二.插入排序
口诀:
1.将数组分为已排序区和待排序区;
2.将已排序区后面的一个元素,向前插入到待排序区;
3.直到待排序区没有元素为止;
void insert_sort(int* arr, int l, int r) {for (int i = l + 1; i < r; i++) {int j = i;while (j > l && arr[j] < arr[j - 1]) {swap(arr[j], arr[j - 1]);j -= 1;}}
}插入排序的优化:无监督的插入排序
优化思想:先将该序列中最小值放到第一位,便可以省略掉while循环中 j > l 的判断条件;
增加了O(n)次的操作, 减少了O()的判断;
//插入排序的优化
void unguarded_insert_sort(int* arr, int l, int r) {int ind = l;for (int i = l + 1; i < r; i++) {if (arr[i] < arr[ind]) ind = i;}//swap(arr[ind], arr[l]); 不可以直接交换,破坏了插入排序的稳定性while (ind > l) {swap(arr[ind], arr[ind - 1]);ind -= 1;}for (int i = l + 2; i < r; i++) {int j = i;while (arr[j] < arr[j - 1]) {swap(arr[j], arr[j - 1]);j -= 1;}}return;
}三.希尔排序(分组插入排序)
口诀:
1.设计一个步长序列;
2.按照步长,对序列进行分组,每组采用插入排序;
3.直到执行到步长为1为止;
//希尔排序
void shell_sort(int* arr, int l, int r) {int k = 2, n = (r - l), step;do {step = n / k == 0? 1 : n / k;for (int i = l; i < l + step; i++) {unguarded_insert_sort(arr, i, r, step);}k *= 2;} while (step != 1);return;
}//希尔排序
void shell_sort_hibbard(int* arr, int l, int r) {int step = 1, n = (r - l);while (step <= n / 2) step = step * 2 + 1;do{step /= 2;for (int i = l; i < l + step; i++) {unguarded_insert_sort(arr, i, r, step);}} while (step > 1);return;
}四.冒泡排序
口诀:
1.将数组分为已排序区和待排序区;
2.从头到扫描待排序区,若前面的元素比后面的元素大,进行交换;
3.每一轮都会将待排序区中的最大值移动到待排序区的最后一位;
4.直到待排序区没有元素为止;
//冒泡排序
void bubble_sort(int* arr, int l, int r) {for (int i = r - 1; i >= l + 1; i--) {for (int j = l; j < i; j++) {if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);} }return;
}冒泡排序的优化思想:若待排序区中已经有序,则停止排序;
//冒泡排序
void bubble_sort(int* arr, int l, int r) {for (int i = r - 1, cnt = 0; i >= l + 1; i--) {cnt = 0;for (int j = l; j < i; j++) {if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); cnt++; }} if (cnt == 0) break;}return;
}五.快速排序
口诀:
1.选择一个基准值;
2.将原有的数组分为两个区域,前一个区域小于等于基准值,后一个区域大于等于基准值(分区操作);
3.红色指针向前移动,直到找到小于基准值的数,放到蓝色指针的位置,随后,蓝色指针向后移动,直到找到大于基准值的数,放到红色指针的位置,循环往复;
4.直到红色指针和蓝色相遇,此时相遇位置就是基准值所在位置;
5.最后再对两个区域重复上述的过程;
//快速排序
void quick_sort(int* arr, int l, int r) {if (r - l <= 2) {if (r - l == 1) return;if (arr[l] > arr[l + 1]) swap(arr[l], arr[l + 1]);return ;}//partitionint x = l, y = r - 1, z = arr[l];while (x < y) {while (x < y && z <= arr[y]) y--;if (x < y) arr[x++] = arr[y];while (x < y && arr[x] <= z) x++;if (x < y) arr[y--] = arr[x];}arr[x] = z;quick_sort(arr, l, x);quick_sort(arr, x + 1, r);return;
}快速排序的优化:
//快速排序的优化1
void more_quick_sort1(int* arr, int l, int r) {if (r - l <= 2) {if (r - l == 1) return;if (arr[l] > arr[l + 1]) swap(arr[l], arr[l + 1]);return ;}//partitionint x = l, y = r - 1, z = arr[l];do {while (arr[x] < z) x++;while (arr[y] > z) y--;if (x <= y) {swap(arr[x], arr[y]);x++, y--;}} while (x <= y);more_quick_sort1(arr, l, x);more_quick_sort1(arr, x, r);return;
}//三点取中法
int three_point_select(int a, int b, int c) {if (a > b) swap(a, b);if (a > c) swap(a, c);if (b > c) swap(b, c);return b;
}//快速排序的优化2
void more_quick_sort2(int* arr, int l, int r) {if (r - l <= 2) {if (r - l == 1) return;if (arr[l] > arr[l + 1]) swap(arr[l], arr[l + 1]);return;}//partitionint x = l, y = r - 1, z = three_point_select(arr[l], arr[r - 1], arr[(l + r) /2]);do {while (arr[x] < z) x++;while (arr[y] > z) y--;if (x <= y) {swap(arr[x], arr[y]);x++, y--;}} while (x <= y);more_quick_sort2(arr, l, x);more_quick_sort2(arr, x, r);return;
}//快速排序的优化3
void more_quick_sort3(int* arr, int l, int r) {if (r - l <= 2) {if (r - l == 1) return;if (arr[l] > arr[l + 1]) swap(arr[l], arr[l + 1]);return;}while (l < r) {//partitionint x = l, y = r - 1, z = three_point_select(arr[l], arr[r - 1], arr[(l + r) / 2]);do {while (arr[x] < z) x++;while (arr[y] > z) y--;if (x <= y) {swap(arr[x], arr[y]);x++, y--;}} while (x <= y);more_quick_sort3(arr, l, x);//单边递归法,只对左半边进行递归l = x;}return;
}//快速排序的优化4
#define threshold 16void __more_quick_sort4(int* arr, int l, int r) {while (r - l > threshold) {//partitionint x = l, y = r - 1, z = three_point_select(arr[l], arr[r - 1], arr[(l + r) / 2]);do {while (arr[x] < z) x++;while (arr[y] > z) y--;if (x <= y) {swap(arr[x], arr[y]);x++, y--;}} while (x <= y);__more_quick_sort4(arr, l, x);//单边递归法,只对左半边进行递归l = x;}return;
}
void more_quick_sort4(int* arr, int l, int r) {__more_quick_sort4(arr, l, r);unguarded_insert_sort(arr, l, r);
}
六.归并排序
归并:
最后将归并后的数组拷贝回原来的数组;
//归并排序
void merge_sort(int* arr, int l, int r) {if (r - l <= 1) return;int mid = (l + r) / 2;merge_sort(arr, l, mid);merge_sort(arr, mid, r);int p1 = l, p2 = mid, k = 0;int* temp = (int*)malloc(sizeof(int) * (r - l));while (p1 < mid || p2 < r) {if (p2 == r || (p1 < mid && arr[p1] <= arr[p2])) {temp[k++] = arr[p1++];}else {temp[k++] = arr[p2++];}}for (int i = l; i < r; i++) arr[i] = temp[i - l];free(temp);return;
}
七.基数排序
原则:相同数字相对位置不变;
1.先统计个位上每个数字出现的个数,并求前缀和;
2.根据前缀和,从后向前扫描,将原数组依次放到相应位置;
3.放置到相应位置时,该数对应的基数的前缀和减一,直到数组遍历完成;
对十位的排序同理.
//基数排序void radix_sort(int* arr, int l, int r) {
#define K 65536int n = r - l;int* cnt = (int*)malloc(sizeof(int) * K); //统计每种数字出现的次数int* temp = (int*)malloc(sizeof(int) * n);//表示排序后的结果//round1memset(cnt, 0, sizeof(int) * K);for (int i = l; i < r; i++) cnt[arr[i] % K] += 1;for (int i = 1; i < K; i++) cnt[i] += cnt[i - 1];for (int i = r - 1; i >= l; i--) temp[--cnt[arr[i] % K]] = arr[i];memcpy(arr + l, temp, sizeof(int) * n);//round2memset(cnt, 0, sizeof(int) * K);for (int i = l; i < r; i++) cnt[arr[i] / K] += 1;for (int i = 1; i < K; i++) cnt[i] += cnt[i - 1];for (int i = r - 1; i >= l; i--) temp[--cnt[arr[i] / K]] = arr[i];memcpy(arr + l, temp, sizeof(int) * n);return;
}八.排序算法总结
排序算法的稳定性:
稳定排序:
相同值的相对顺序不会进行改变;
插入排序, 冒泡排序, 归并排序, 基数排序;
非稳定排序:
选择排序, 希尔排序, 快速排序, 堆排序;
排序算法的内外部特性:
看排序算法的过程中是否使用到了额外的存储空间;
内部排序:
插入排序, 冒泡排序, 选择排序, 希尔排序, 快速排序, 堆排序;
外部排序:
归并排序, 基数排序;
九.C++中sort函数的使用
void output(int* arr, int n, const char* s = "arr") {printf("%s[%lu] = ", s, n);for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return;
}void test1() {//sort arrayint* arr = getRandData(10);output(arr, 10);sort(arr, arr + 10);//从小到大排序;output(arr, 10);sort(arr, arr + 10, greater<int>());//从大到小排序;output(arr, 10);free(arr);return;
}void output(vector<int> arr) {printf("arr[%lu] = ", arr.size());for (int i = 0; i < arr.size(); i++) {printf("%d ", arr[i]);}printf("\n");return;
}void test2() {//sort vectorvector<int> arr;for (int i = 0; i < 10; i++) arr.push_back(rand() % 10000);output(arr);sort(arr.begin(), arr.end());output(arr);sort(arr.begin(), arr.end(), greater<int>());//output(arr);return;
}struct Data {int x, y;
};ostream& operator<<(ostream& out, const Data& d) {out << "(" << d.x << "," << d.y << ")";return out;
}
template<typename T>void output(vector<T> &arr) {printf("arr[%lu] = ", arr.size());for (int i = 0; i < arr.size(); i++) {cout << arr[i] << " ";}printf("\n");return;
}bool cmp(const Data& a, const Data& b) {if (a.x != b.x) return a.x < b.x;return a.y > b.y;
}//返回什么样的表达式, 排序规则就是怎么样的
//以上先按x从小到大排,再按y从大到小排void test3() {//sort my data structurevector<Data> arr;for (int i = 0; i < 10; i++) {Data d;d.x = rand() % 10, d.y = rand() % 10;arr.push_back(d);}output(arr);sort(arr.begin(), arr.end(), cmp);output(arr);return;
}void test4() {//对数组进行排序,但是又不对数组进行改变//可以对数组的下标进行排序int* arr = getRandData(10);int* ind = getRandData(10);for (int i = 0; i < 10; i++) ind[i] = i;output(arr, 10);sort(ind, ind + 10, [&](int i, int j) -> bool {return arr[i] < arr[j];});output(arr, 10);output(ind, 10, "ind");
}int main() {test1();test2();test3();test4();return 0;
}代码练习
1. 两数之和 - 力扣（LeetCode）
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();vector<int> ind(n);for(int i = 0; i < n; i++) ind[i] = i;sort(ind.begin(), ind.end(), [&](int i, int j) -> bool {return nums[i] < nums[j];});int p1 = 0, p2 = n - 1;while(nums[ind[p1]] + nums[ind[p2]] != target) {if(nums[ind[p1]] + nums[ind[p2]] < target) p1 += 1;else p2 -= 1;}vector<int> ret(2);ret[0] = ind[p1], ret[1] = ind[p2];return ret;}
};148. 排序链表 - 力扣（LeetCode）
快速排序解法:
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {if(head == nullptr || head->next == nullptr) return head;int l = head->val, r = head->val, z;ListNode* p = head, *h1 = nullptr, *h2 = nullptr, *q;while(p) l = min(p->val, l), r = max(p->val, r) , p = p->next;z = (l + r) >> 1;if(l == r) return head;p = head;while(p) {q = p->next;if(p->val <= z) {p->next = h1;h1 = p;} else {p->next = h2;h2 = p;}p = q;}h1 = sortList(h1);h2 = sortList(h2);p = h1;while(p->next) p = p->next;p->next = h2;return h1;}
};归并排序解法:
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:int getLength(ListNode*head) {int n = 0;while(head) n += 1, head = head->next;return n;}ListNode* merge_sort(ListNode *head, int n) {if(n <= 1) return head;int l = n /2 , r = n - l;ListNode* p = head, *p1, *p2, ret;for(int i = 1; i < l; i++) p = p->next;p1 = head; p2 = p->next;p->next = NULL;p1 = merge_sort(p1, l);p2 = merge_sort(p2, r);p = &ret ; ret.next = NULL;while(p1 || p2) {if(p2 == NULL || (p1 && (p1->val <= p2->val )) ) {p->next = p1;p = p1;p1 = p1->next;} else {p->next = p2;p = p2;p2 = p2->next;}}return ret.next;}ListNode* sortList(ListNode* head) {int n = getLength(head);return merge_sort(head, n);}
};88. 合并两个有序数组 - 力扣（LeetCode）
class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int p1 = m - 1, p2 = n -1, k = m + n - 1;while(p1 != -1 || p2 != -1) {if(p2 == -1 || (p1 != -1 &&(nums1[p1] > nums2[p2]))) {nums1[k--] = nums1[p1--];} else {nums1[k--] = nums2[p2--];}}return;}
};21. 合并两个有序链表 - 力扣（LeetCode）
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode ret, *p = &ret;while(list1 || list2) {if(list2 == NULL|| (list1 && (list1->val < list2->val))) {p->next = list1;list1 = list1->next;p = p->next;} else {p->next = list2;list2 = list2->next;p = p->next;}}return ret.next;}
};219. 存在重复元素 II - 力扣（LeetCode）
class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {int n = nums.size();vector<int> ind(n);for(int i = 0; i < n; i++) ind[i] = i;sort(ind.begin(), ind.end() , [&](int i, int j) -> bool {if(nums[i] != nums[j]) return nums[i] < nums[j];return i < j;});for(int i = 0; i < n - 1; i++) {if(nums[ind[i]] - nums[ind[i + 1]]) continue;if(ind[i + 1] - ind[i] <= k)return true;}return false;}
};士兵 - 题目 - Online Judge
#define _CRT_SECURE_NO_WARNINGS#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;int main() {int n;cin >> n;vector<int> x(n), y(n);for (int i = 0; i < n; i++) {cin >> x[i] >> y[i];}sort(x.begin(), x.end());for (int i = 0; i < n; i++) x[i] -= i;sort(x.begin(), x.end());sort(y.begin(), y.end());int costX = 0, costY = 0;for (int i = 0; i < n; i++) {costX += abs(x[i] - x[n/2]);costY += abs(y[i] - y[n/2]);}cout << costX + costY << endl;return 0;
}国王游戏 - 题目 - Online Judge
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>using namespace std;#define MAX_N 1000
int a[MAX_N + 5], b[MAX_N + 5], ind[MAX_N + 5];class BigInt : public vector<int> {
public :BigInt(int x) {this->push_back(x);proccess_digit();}BigInt operator/(int x) {BigInt ret(*this);int y = 0;for (int i = size() - 1; i >= 0; i--) {y = y * 10 + at(i);ret[i] = y / x;y %= x;}ret.proccess_digit();return ret;}void operator*=(int x) {for (int i = 0; i < size(); i++) at(i) *= x;proccess_digit(); return;}bool operator>(const BigInt& a) const {if (size() != a.size()) return size() > a.size();for (int i = size() - 1; i >= 0; i--) {if (at(i) != a[i]) return at(i) > a[i];}return false;}void proccess_digit() {for (int i = 0; i < size(); i++) {if (at(i) < 10) continue;if (i + 1 == size())this->push_back(0);at(i + 1) += at(i) / 10;at(i) %= 10;}while (size() > 1 && at(size() - 1) == 0)this->pop_back();return;}
};ostream& operator<<(ostream& out, const BigInt& a) {for (int i = a.size() - 1; i >= 0; i--) {out << a[i];}return out;
}int main() {int n;cin >> n;for (int i = 0; i < n + 1; i++) {cin >> a[i] >> b[i];ind[i] = i;}sort(ind + 1, ind + n + 1, [&](int i, int j) -> bool {return a[i] * b[i] < a[j] * b[j];});BigInt ans = 0, p = a[0], temp = 0;for (int i = 1; i < n + 1; i++) {temp = p / b[ind[i]];if (temp > ans) ans = temp;p *= a[ind[i]];}cout << ans << endl;return 0;
}