/*
（無序區(qū)撤奸，有序區(qū)）啸驯。從無序區(qū)通過交換找出最大元素放到有序區(qū)前端。
選擇排序思路：
1. 比較相鄰的元素英上。如果第一個(gè)比第二個(gè)大炭序，就交換他們兩個(gè)啤覆。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對惭聂。這步做完后窗声，最后的元素會是最大的數(shù)。
3. 針對所有的元素重復(fù)以上的步驟辜纲，除了最后一個(gè)笨觅。
4. 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較耕腾。
*/
// 冒泡排序
void BubbleSort(vector<int>& v) {
int len = v.size();
for (int i = 0; i < len - 1; ++i)
for (int j = 0; j < len - 1 - i; ++j)
if (v[j] > v[j + 1])
swap(v[j], v[j + 1]);
}
// 模板實(shí)現(xiàn)冒泡排序
template<typename T> //整數(shù)或浮點(diǎn)數(shù)皆可使用,若要使用物件(class)時(shí)必須設(shè)定大於(>)的運(yùn)算子功能
void bubble_sort(T arr[], int len) {
for (int i = 0; i < len - 1; i++)
for (int j = 0; j < len - 1 - i; j++)
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
// 冒泡排序（改進(jìn)版）
void BubbleSort_orderly(vector<int>& v) {
int len = v.size();
bool orderly = false;
for (int i = 0; i < len - 1 && !orderly; ++i) {
orderly = true;
for (int j = 0; j < len - 1 - i; ++j) {
if (v[j] > v[j + 1]) {? // 從小到大
orderly = false; // 發(fā)生交換則仍非有序
swap(v[j], v[j + 1]);
}
}
}
}
（有序區(qū)见剩，無序區(qū)）。在無序區(qū)里找一個(gè)最小的元素跟在有序區(qū)的后面幽邓。對數(shù)組：比較得多炮温，換得少。
選擇排序思路：
1. 在未排序序列中找到最星６妗（大）元素柒啤，存放到排序序列的起始位置
2. 從剩余未排序元素中繼續(xù)尋找最小（大）元素畸颅，然后放到已排序序列的末尾
3. 以此類推担巩，直到所有元素均排序完畢
*/
// 選擇排序
void SelectionSort(vector<int>& v) {
int min, len = v.size();
for (int i = 0; i < len - 1; ++i) {
min = i;
for (int j = i + 1; j < len; ++j) {
if (v[j] < v[min]) {? ? // 標(biāo)記最小的
min = j;
}
}
if (i != min)? // 交換到前面
swap(v[i], v[min]);
}
}
// 模板實(shí)現(xiàn)
template<typename T>
void Selection_Sort(std::vector<T>& arr) {
int len = arr.size();
for (int i = 0; i < len - 1; i++) {
int min = i;
for (int j = i + 1; j < len; j++)
if (arr[j] < arr[min])
min = j;
if(i != min)
std::swap(arr[i], arr[min]);
}
}
（有序區(qū)，無序區(qū)）没炒。把無序區(qū)的第一個(gè)元素插入到有序區(qū)的合適的位置涛癌。對數(shù)組：比較得少，換得多送火。
插入排序思路：
1. 從第一個(gè)元素開始拳话，該元素可以認(rèn)為已經(jīng)被排序
2. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
3. 如果該元素（已排序）大于新元素种吸，將該元素移到下一位置
4. 重復(fù)步驟3弃衍，直到找到已排序的元素小于或者等于新元素的位置
5. 將新元素插入到該位置后
6. 重復(fù)步驟2~5
*/
// 插入排序
void InsertSort(vector<int>& v)
{
? ? int len = v.size();
for (int i = 1; i < len - 1; ++i) {
int temp = v[i];
? ? ? ? for(int j = i - 1; j >= 0; --j)
? ? ? ? {
? ? ? ? ? ? if(v[j] > temp)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? v[j + 1] = v[j];
? ? ? ? ? ? ? ? v[j] = temp;
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? ? ? break;
? ? ? ? }
}
}
（小數(shù)，基準(zhǔn)元素坚俗，大數(shù)）镜盯。在區(qū)間中隨機(jī)挑選一個(gè)元素作基準(zhǔn)，將小于基準(zhǔn)的元素放在基準(zhǔn)之前猖败，大于基準(zhǔn)的元素放在基準(zhǔn)之后速缆，再分別對小數(shù)區(qū)與大數(shù)區(qū)進(jìn)行排序。
快速排序思路：
1. 選取第一個(gè)數(shù)為基準(zhǔn)
2. 將比基準(zhǔn)小的數(shù)交換到前面恩闻，比基準(zhǔn)大的數(shù)交換到后面
3. 對左右區(qū)間重復(fù)第二步艺糜，直到各區(qū)間只有一個(gè)數(shù)
*/
// ----------------------------------------------------
// 快速排序（遞歸）
void QuickSort(vector<int>& v, int low, int high) {
if (low >= high) // 結(jié)束標(biāo)志
return;
int first = low; // 低位下標(biāo)
int last = high; // 高位下標(biāo)
int key = v[first]; // 設(shè)第一個(gè)為基準(zhǔn)
while (first < last)
{
// 將比第一個(gè)小的移到前面
while (first < last && v[last] >= key)
last--;
if (first < last)
v[first++] = v[last];
// 將比第一個(gè)大的移到后面
while (first < last && v[first] <= key)
first++;
if (first < last)
v[last--] = v[first];
}
// 基準(zhǔn)置位
v[first] = key;
// 前半遞歸
QuickSort(v, low, first - 1);
// 后半遞歸
QuickSort(v, first + 1, high);
}
// ----------------------------------------------------
// 模板實(shí)現(xiàn)快速排序（遞歸）
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> //整數(shù)或浮點(diǎn)數(shù)皆可使用,若要使用物件(class)時(shí)必須設(shè)定"小於"(<)、"大於"(>)、"不小於"(>=)的運(yùn)算子功能
void quick_sort(T arr[], int len) {
? ? quick_sort_recursive(arr, 0, len - 1);
}
// ----------------------------------------------------
// 模板實(shí)現(xiàn)快速排序（迭代）
struct Range {
? ? int start, end;
? ? Range(int s = 0, int e = 0) {
? ? ? ? start = s, end = e;
? ? }
};
template <typename T> // 整數(shù)或浮點(diǎn)數(shù)皆可使用,若要使用物件(class)時(shí)必須設(shè)定"小於"(<)倦踢、"大於"(>)送滞、"不小於"(>=)的運(yùn)算子功能
void quick_sort(T arr[], const int len) {
? ? if (len <= 0)
? ? ? ? return; // 避免len等於負(fù)值時(shí)宣告堆疊陣列當(dāng)機(jī)
? ? // 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);
? ? }
}
#include <iostream>
#include <algorithm>
using namespace std;
// 堆排序：（最大堆，有序區(qū)）辱挥。從堆頂把根卸出來放在有序區(qū)之前犁嗅，再恢復(fù)堆。
void max_heapify(int arr[], int start, int end) {
//建立父節(jié)點(diǎn)指標(biāo)和子節(jié)點(diǎn)指標(biāo)
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { //若子節(jié)點(diǎn)指標(biāo)在範(fàn)圍內(nèi)才做比較
if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個(gè)子節(jié)點(diǎn)大小晤碘，選擇最大的
son++;
if (arr[dad] > arr[son]) //如果父節(jié)點(diǎn)大於子節(jié)點(diǎn)代表調(diào)整完畢褂微，直接跳出函數(shù)
return;
else { //否則交換父子內(nèi)容再繼續(xù)子節(jié)點(diǎn)和孫節(jié)點(diǎn)比較
swap(arr[dad], arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len) {
//初始化，i從最後一個(gè)父節(jié)點(diǎn)開始調(diào)整
for (int i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
//先將第一個(gè)元素和已經(jīng)排好的元素前一位做交換园爷，再從新調(diào)整(剛調(diào)整的元素之前的元素)宠蚂，直到排序完畢
for (int i = len - 1; i > 0; i--) {
swap(arr[0], arr[i]);
max_heapify(arr, 0, i - 1);
}
}
int main() {
int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
for (int i = 0; i < len; i++)
cout << arr[i] << ' ';
cout << endl;
return 0;
}
// 歸并排序：把數(shù)據(jù)分為兩段，從兩段中逐個(gè)選最小的元素移入新數(shù)據(jù)段的末尾童社∏蟛蓿可從上到下或從下到上進(jìn)行。
/*****************
? ? 迭代版
*****************/
//整數(shù)或浮點(diǎn)數(shù)皆可使用,若要使用物件(class)時(shí)必須設(shè)定"小於"(<)的運(yùn)算子功能
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;
}
/*****************
? ? 遞歸版
*****************/
template<typename T>
void merge_sort_recursive(T arr[], T reg[], int start, int end) {
if (start >= end)
return;
int len = end - start, mid = (len >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2)
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
while (start1 <= end1)
reg[k++] = arr[start1++];
while (start2 <= end2)
reg[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = reg[k];
}
//整數(shù)或浮點(diǎn)數(shù)皆可使用,若要使用物件(class)時(shí)必須設(shè)定"小於"(<)的運(yùn)算子功能
template<typename T>
void merge_sort(T arr[], const int len) {
T *reg = new T[len];
merge_sort_recursive(arr, reg, 0, len - 1);
delete[] reg;
}
// 希爾排序：每一輪按照事先決定的間隔進(jìn)行插入排序扰楼，間隔會依次縮小呀癣，最后一次一定要是1。
template<typename T>
void shell_sort(T array[], int length) {
? ? int h = 1;
? ? while (h < length / 3) {
? ? ? ? h = 3 * h + 1;
? ? }
? ? while (h >= 1) {
? ? ? ? for (int i = h; i < length; i++) {
? ? ? ? ? ? for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
? ? ? ? ? ? ? ? std::swap(array[j], array[j - h]);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? h = h / 3;
? ? }
}
/*****************
計(jì)數(shù)排序：統(tǒng)計(jì)小于等于該元素值的元素的個(gè)數(shù)i弦赖，于是該元素就放在目標(biāo)數(shù)組的索引i位（i≥0）项栏。
計(jì)數(shù)排序基于一個(gè)假設(shè)，待排序數(shù)列的所有數(shù)均出現(xiàn)在（0蹬竖，k）的區(qū)間之內(nèi)沼沈，如果k過大則會引起較大的空間復(fù)雜度
計(jì)數(shù)排序并非是一種基于比較的排序方法，它直接統(tǒng)計(jì)出鍵值本應(yīng)該出現(xiàn)的位置
時(shí)間復(fù)雜度為O（n）币厕，空間復(fù)雜度為O（n+k）
*****************/
#include<iostream>
#include<vector>
using namespace std;
void countSort(vector<int>& vec,vector<int>& objVec)
{
vector<int> range(10,0);? ? //range的下標(biāo)即鍵值
for(int i=0;i<vec.size();++i)
{//統(tǒng)計(jì)每個(gè)鍵值出現(xiàn)的次數(shù)
range[vec[i]]++;
}
for(int i=1;i<vec.size();++i)
{//后面的鍵值出現(xiàn)的位置為前面所有鍵值出現(xiàn)的次數(shù)之和
range[i]+=range[i-1];
}
//至此列另，range中存放的是相應(yīng)鍵值應(yīng)該出現(xiàn)的位置
int length=vec.size();
for(int i=length-1;i>=0;--i)? ? ? ? //注意一個(gè)小細(xì)節(jié)，統(tǒng)計(jì)時(shí)最正序的旦装，這里是逆序
{//如果存在相同的鍵值访递，為了保持穩(wěn)定性，后出現(xiàn)的應(yīng)該還是位于后面
//如果正序同辣，則先出現(xiàn)的會放置到后面，因此不再穩(wěn)定
objVec[range[vec[i]]]=vec[i];? //將鍵值放到目標(biāo)位置
range[vec[i]]--;
}
}
int main()
{
int a[14]={0,5,7,9,6,3,4,5,2,8,6,9,2,1};
vector<int> vec(a,a+14);
vector<int> objVec(14,0);
countSort(vec,objVec);
for(int i=0;i<objVec.size();++i)
cout<<objVec[i]<<"? ";
cout<<endl;
return 0;
}
#include<iterator>
#include<iostream>
#include<vector>
using std::vector;
/*****************
桶排序：將值為i的元素放入i號桶惭载，最后依次把桶里的元素倒出來旱函。
桶排序序思路：
1. 設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶子。
2. 尋訪序列描滔，并且把項(xiàng)目一個(gè)一個(gè)放到對應(yīng)的桶子去棒妨。
3. 對每個(gè)不是空的桶子進(jìn)行排序。
4. 從不是空的桶子里把項(xiàng)目再放回原來的序列中。
假設(shè)數(shù)據(jù)分布在[0券腔，100)之間伏穆，每個(gè)桶內(nèi)部用鏈表表示，在數(shù)據(jù)入桶的同時(shí)插入排序纷纫，然后把各個(gè)桶中的數(shù)據(jù)合并枕扫。
*****************/
const int BUCKET_NUM = 10;
struct ListNode{
explicit ListNode(int i=0):mData(i),mNext(NULL){}
ListNode* mNext;
int mData;
};
ListNode* insert(ListNode* head,int val){
ListNode dummyNode;
ListNode *newNode = new ListNode(val);
ListNode *pre,*curr;
dummyNode.mNext = head;
pre = &dummyNode;
curr = head;
while(NULL!=curr && curr->mData<=val){
pre = curr;
curr = curr->mNext;
}
newNode->mNext = curr;
pre->mNext = newNode;
return dummyNode.mNext;
}
ListNode* Merge(ListNode *head1,ListNode *head2){
ListNode dummyNode;
ListNode *dummy = &dummyNode;
while(NULL!=head1 && NULL!=head2){
if(head1->mData <= head2->mData){
dummy->mNext = head1;
head1 = head1->mNext;
}else{
dummy->mNext = head2;
head2 = head2->mNext;
}
dummy = dummy->mNext;
}
if(NULL!=head1) dummy->mNext = head1;
if(NULL!=head2) dummy->mNext = head2;
return dummyNode.mNext;
}
void BucketSort(int n,int arr[]){
vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));
for(int i=0;i<n;++i){
int index = arr[i]/BUCKET_NUM;
ListNode *head = buckets.at(index);
buckets.at(index) = insert(head,arr[i]);
}
ListNode *head = buckets.at(0);
for(int i=1;i<BUCKET_NUM;++i){
head = Merge(head,buckets.at(i));
}
for(int i=0;i<n;++i){
arr[i] = head->mData;
head = head->mNext;
}
}
// 基數(shù)排序：一種多關(guān)鍵字的排序算法，可用桶排序?qū)崿F(xiàn)辱魁。
int maxbit(int data[], int n) //輔助函數(shù)烟瞧，求數(shù)據(jù)的最大位數(shù)
{
? ? int maxData = data[0]; ///< 最大數(shù)
? ? /// 先求出最大數(shù)，再求其位數(shù)染簇，這樣有原先依次每個(gè)數(shù)判斷其位數(shù)参滴，稍微優(yōu)化點(diǎn)。
? ? for (int i = 1; i < n; ++i)
? ? {
? ? ? ? if (maxData < data[i])
? ? ? ? ? ? maxData = data[i];
? ? }
? ? int d = 1;
? ? int p = 10;
? ? while (maxData >= p)
? ? {
? ? ? ? //p *= 10; // Maybe overflow
? ? ? ? maxData /= 10;
? ? ? ? ++d;
? ? }
? ? return d;
/*? ? int d = 1; //保存最大的位數(shù)
? ? int p = 10;
? ? for(int i = 0; i < n; ++i)
? ? {
? ? ? ? while(data[i] >= p)
? ? ? ? {
? ? ? ? ? ? p *= 10;
? ? ? ? ? ? ++d;
? ? ? ? }
? ? }
? ? return d;*/
}
void radixsort(int data[], int n) //基數(shù)排序
{
? ? int d = maxbit(data, n);
? ? int *tmp = new int[n];
? ? int *count = new int[10]; //計(jì)數(shù)器
? ? int i, j, k;
? ? int radix = 1;
? ? for(i = 1; i <= d; i++) //進(jìn)行d次排序
? ? {
? ? ? ? for(j = 0; j < 10; j++)
? ? ? ? ? ? count[j] = 0; //每次分配前清空計(jì)數(shù)器
? ? ? ? for(j = 0; j < n; j++)
? ? ? ? {
? ? ? ? ? ? k = (data[j] / radix) % 10; //統(tǒng)計(jì)每個(gè)桶中的記錄數(shù)
? ? ? ? ? ? count[k]++;
? ? ? ? }
? ? ? ? for(j = 1; j < 10; j++)
? ? ? ? ? ? count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個(gè)桶
? ? ? ? for(j = n - 1; j >= 0; j--) //將所有桶中記錄依次收集到tmp中
? ? ? ? {
? ? ? ? ? ? k = (data[j] / radix) % 10;
? ? ? ? ? ? tmp[count[k] - 1] = data[j];
? ? ? ? ? ? count[k]--;
? ? ? ? }
? ? ? ? for(j = 0; j < n; j++) //將臨時(shí)數(shù)組的內(nèi)容復(fù)制到data中
? ? ? ? ? ? data[j] = tmp[j];
? ? ? ? radix = radix * 10;
? ? }
? ? delete []tmp;
? ? delete []count;
}
