1 常见的排序算法
排序算法概况-菜鸟教程
2 实现方法
2.1 冒泡排序
步骤思路： 比较相邻的元素，如果第一个比第二个大，就交换他们两个，再比较交换后的第二个和第三个，直到最大的一个元素到最后。
菜鸟教程-动图演示
#include <iostream>
using namespace std;
int main() {
int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
int len = (int) sizeof(arr) / sizeof(*arr);
// 冒泡排序
for (int i=0; i<len-1; i++) {
for (int j=0; j<len-1-i; j++){
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = a[j+1];
arr[j+1] = temp;
}
}
}
for (int i=0; i<len; i++) {
cout<<arr[i] << ' ';
}
}
2.2 选择排序
步骤思路：首先在
未排序序列中找到最大（小）元素，存放到排序序列的起始位置，再从剩余的未排序的元素中继续寻找最大（小）的元素，放到已排序序列的末尾。
相当于将序列分为两部分，在未排序的部分选择符合规则的元素，放到有序的部分。
菜鸟教程-动图演示
#include<iostream>
using namespace std;
int main() {
int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
// 选择排序
for (int i=0; i<arr.size()-1; i++) {
int min = i;
for(int j=i+1; j<arr.size(); j++) {
if (arr[j] < arr[min])
min = j;
}
swap(arr[i], arr[min]);
}
}
2.3 插入排序
步骤思路：还是将整个序列看成两部分，已经有序部分和待排序部分，从头到尾依次扫描未排序序列，将扫描的元素插入到有序序列的适当位置。（相同大小往后放）
菜鸟教程-动图演示
#include<iostream>
using namespace std;
int main() {
int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
// 插入排序
for (int i=1; i<arr.size(); i++) {
int key = arr[i];
int j = i-1;
while((j>=0) && (key<arr[j])) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
2.4 归并排序
步骤思路：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤 3 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。
菜鸟教程-动图演示
// 迭代法
template<typename T>
void merge_sort(T arr[], int len) {
T *a = arr;
T *b = new T[len];
for (int seg = 1; seg < len; seg += seg) {
for (int start = 0; start < len; start += seg + seg) {
int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
while (start1 < end1)
b[k++] = a[start1++];
while (start2 < end2)
b[k++] = a[start2++];
}
T *temp = a;
a = b;
b = temp;
}
if (a != arr) {
for (int i = 0; i < len; i++)
b[i] = a[i];
b = a;
}
delete[] b;
}
// 递归法
void Merge(vector<int> &Array, int front, int mid, int end) {
// preconditions:
// Array[front...mid] is sorted
// Array[mid+1 ... end] is sorted
// Copy Array[front ... mid] to LeftSubArray
// Copy Array[mid+1 ... end] to RightSubArray
vector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);
vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);
int idxLeft = 0, idxRight = 0;
LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());
RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());
// Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
for (int i = front; i <= end; i++) {
if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) {
Array[i] = LeftSubArray[idxLeft];
idxLeft++;
} else {
Array[i] = RightSubArray[idxRight];
idxRight++;
}
}
}
void MergeSort(vector<int> &Array, int front, int end) {
if (front >= end)
return;
int mid = (front + end) / 2;
MergeSort(Array, front, mid);
MergeSort(Array, mid + 1, end);
Merge(Array, front, mid, end);
}
2.5 快速排序
步骤思路：从序列中挑选一个元素作为基准，重新排序，比基准小的放前面， 比基准大的放右边。
递归把小于基准值元素子数列和大于基准值元素的子数列排序。
菜鸟教程-动图演示
// 迭代法
struct Range {
int start, end;
Range(int s = 0, int e = 0) {
start = s, end = e;
}
};
template <typename T>
void quick_sort(T arr[], const int len) {
if (len <= 0)
return; // 避免len等於負值時宣告堆疊陣列當機
// r[]模擬堆疊,p為數量,r[p++]為push,r[--p]為pop且取得元素
Range r[len];
int p = 0;
r[p++] = Range(0, len - 1);
while (p) {
Range range = r[--p];
if (range.start >= range.end)
continue;
T mid = arr[range.end];
int left = range.start, right = range.end - 1;
while (left < right) {
while (arr[left] < mid && left < right) left++;
while (arr[right] >= mid && left < right) right--;
std::swap(arr[left], arr[right]);
}
if (arr[left] >= arr[range.end])
std::swap(arr[left], arr[range.end]);
else
left++;
r[p++] = Range(range.start, left - 1);
r[p++] = Range(left + 1, range.end);
}
}
// 递归法
template <typename T>
void quick_sort_recursive(T arr[], int start, int end) {
if (start >= end)
return;
T mid = arr[end];
int left = start, right = end - 1;
while (left < right) { //在整个范围内搜寻比枢纽元值小或大的元素，然后将左侧元素与右侧元素交换
while (arr[left] < mid && left < right) //试图在左侧找到一个比枢纽元更大的元素
left++;
while (arr[right] >= mid && left < right) //试图在右侧找到一个比枢纽元更小的元素
right--;
std::swap(arr[left], arr[right]); //交换元素
}
if (arr[left] >= arr[end])
std::swap(arr[left], arr[end]);
else
left++;
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}
template <typename T>
void quick_sort(T arr[], int len) {
quick_sort_recursive(arr, 0, len - 1);
}
OJ技巧
在进行OJ的时候要善于对于复杂的数据形式利用结构体和sort函数，定义比较规则。
举个例子，对学生信息（包括姓名、年龄、成绩）进行排序
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
struct E {
char name[101];
int age;
int score;
}buf[1000];
// 实现比较规则
bool cmp(E a, E b) {
// 分数不同，分数低的在前
if(a.score != b.score)
return a.score < b.score;
int tmp = strcmp(a.name, b.name);
// 分数相同，名字字典在前的在前
if (tmp != 0)
return tmp < 0;
else
// 名字相同，年龄小的在前
return a.age < b.age
}
int main() {
int n;
while(scanf (%d, &n) != EOF) {
for (int i=0; i<n; i++) {
cin >> buf[i].name >> &buf[i].age, &buf[i].score;
}
// 利用自己定义的规则排序
sort(buf, buf+n, cmp);
for(int i=0; i<n; i++) {
cout<<buf[i].name<<buf[i].age<<buf[i].score<< endl;
}
}
return 0;
}
