1 常見的排序算法
排序算法概況-菜鳥教程
2 實現(xiàn)方法
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 選擇排序
步驟思路：首先在
未排序序列中找到最大（猩浩础）元素，存放到排序序列的起始位置流炕，再從剩余的未排序的元素中繼續(xù)尋找最大（信煜帧）的元素，放到已排序序列的末尾每辟。
相當于將序列分為兩部分剑辫，在未排序的部分選擇符合規(guī)則的元素，放到有序的部分渠欺。
菜鳥教程-動圖演示
#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 插入排序
步驟思路：還是將整個序列看成兩部分妹蔽，已經(jīng)有序部分和待排序部分，從頭到尾依次掃描未排序序列挠将，將掃描的元素插入到有序序列的適當位置讹开。（相同大小往后放）
菜鳥教程-動圖演示
#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 歸并排序
步驟思路：
- 申請空間，使其大小為兩個已經(jīng)排序序列之和捐名，該空間用來存放合并后的序列旦万；
- 設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置镶蹋；
- 比較兩個指針所指向的元素成艘，選擇相對小的元素放入到合并空間，并移動指針到下一位置贺归；
- 重復步驟 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 快速排序
步驟思路：從序列中挑選一個元素作為基準秋冰，重新排序，比基準小的放前面婶熬， 比基準大的放右邊剑勾。
遞歸把小于基準值元素子數(shù)列和大于基準值元素的子數(shù)列排序。
菜鳥教程-動圖演示
// 迭代法
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為數(shù)量,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) { //在整個范圍內(nèi)搜尋比樞紐元值小或大的元素赵颅，然后將左側(cè)元素與右側(cè)元素交換
while (arr[left] < mid && left < right) //試圖在左側(cè)找到一個比樞紐元更大的元素
left++;
while (arr[right] >= mid && left < right) //試圖在右側(cè)找到一個比樞紐元更小的元素
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的時候要善于對于復雜的數(shù)據(jù)形式利用結(jié)構(gòu)體和sort函數(shù)虽另，定義比較規(guī)則。
舉個例子饺谬，對學生信息（包括姓名捂刺、年齡、成績）進行排序
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
struct E {
char name[101];
int age;
int score;
}buf[1000];
// 實現(xiàn)比較規(guī)則
bool cmp(E a, E b) {
// 分數(shù)不同，分數(shù)低的在前
if(a.score != b.score)
return a.score < b.score;
int tmp = strcmp(a.name, b.name);
// 分數(shù)相同族展，名字字典在前的在前
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;
}
// 利用自己定義的規(guī)則排序
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;
}
