c++排序

/*

（无序区，有序区）。从无序区通过交换找出最大元素放到有序区前端。

选择排序思路：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3. 针对所有的元素重复以上的步骤，除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

*/

// 冒泡排序

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]);

}

// 模板实现冒泡排序

template<typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定大於(>)的運算子功能

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]);

}

// 冒泡排序（改进版）

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; // 发生交换则仍非有序

swap(v[j], v[j + 1]);

}

}

}

}

（有序区，无序区）。在无序区里找一个最小的元素跟在有序区的后面。对数组：比较得多，换得少。

选择排序思路：

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾

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]) {    // 标记最小的

min = j;

}

}

if (i != min)  // 交换到前面

swap(v[i], v[min]);

}

}

// 模板实现

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]);

}

}

（有序区，无序区）。把无序区的第一个元素插入到有序区的合适的位置。对数组：比较得少，换得多。

插入排序思路：

1. 从第一个元素开始，该元素可以认为已经被排序

2. 取出下一个元素，在已经排序的元素序列中从后向前扫描

3. 如果该元素（已排序）大于新元素，将该元素移到下一位置

4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

5. 将新元素插入到该位置后

6. 重复步骤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;

        }

}

}

（小数，基准元素，大数）。在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。

快速排序思路：

1. 选取第一个数为基准

2. 将比基准小的数交换到前面，比基准大的数交换到后面

3. 对左右区间重复第二步，直到各区间只有一个数

*/

// ----------------------------------------------------

// 快速排序（递归）

void QuickSort(vector<int>& v, int low, int high) {

if (low >= high) // 结束标志

return;

int first = low; // 低位下标

int last = high; // 高位下标

int key = v[first]; // 设第一个为基准

while (first < last)

{

// 将比第一个小的移到前面

while (first < last && v[last] >= key)

last--;

if (first < last)

v[first++] = v[last];

// 将比第一个大的移到后面

while (first < last && v[first] <= key)

first++;

if (first < last)

v[last--] = v[first];

}

// 基准置位

v[first] = key;

// 前半递归

QuickSort(v, low, first - 1);

// 后半递归

QuickSort(v, first + 1, high);

}

// ----------------------------------------------------

// 模板实现快速排序（递归）

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> //整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能

void quick_sort(T arr[], int len) {

    quick_sort_recursive(arr, 0, len - 1);

}

// ----------------------------------------------------

// 模板实现快速排序（迭代）

struct Range {

    int start, end;

    Range(int s = 0, int e = 0) {

        start = s, end = e;

    }

};

template <typename T> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能

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);

    }

}

#include <iostream>

#include <algorithm>

using namespace std;

// 堆排序：（最大堆，有序区）。从堆顶把根卸出来放在有序区之前，再恢复堆。

void max_heapify(int arr[], int start, int end) {

//建立父節點指標和子節點指標

int dad = start;

int son = dad * 2 + 1;

while (son <= end) { //若子節點指標在範圍內才做比較

if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個子節點大小，選擇最大的

son++;

if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數

return;

else { //否則交換父子內容再繼續子節點和孫節點比較

swap(arr[dad], arr[son]);

dad = son;

son = dad * 2 + 1;

}

}

}

void heap_sort(int arr[], int len) {

//初始化，i從最後一個父節點開始調整

for (int i = len / 2 - 1; i >= 0; i--)

max_heapify(arr, i, len - 1);

//先將第一個元素和已经排好的元素前一位做交換，再從新調整(刚调整的元素之前的元素)，直到排序完畢

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;

}

// 归并排序：把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行。

/*****************

    迭代版

*****************/

//整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)的運算子功能

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];

}

//整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)的運算子功能

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;

}

// 希尔排序：每一轮按照事先决定的间隔进行插入排序，间隔会依次缩小，最后一次一定要是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;

    }

}

/*****************

计数排序：统计小于等于该元素值的元素的个数i，于是该元素就放在目标数组的索引i位（i≥0）。

计数排序基于一个假设，待排序数列的所有数均出现在（0，k）的区间之内，如果k过大则会引起较大的空间复杂度

计数排序并非是一种基于比较的排序方法，它直接统计出键值本应该出现的位置

时间复杂度为O（n），空间复杂度为O（n+k）

*****************/

#include<iostream>

#include<vector>

using namespace std;

void countSort(vector<int>& vec,vector<int>& objVec)

{

vector<int> range(10,0);    //range的下标即键值

for(int i=0;i<vec.size();++i)

{//统计每个键值出现的次数

range[vec[i]]++;

}

for(int i=1;i<vec.size();++i)

{//后面的键值出现的位置为前面所有键值出现的次数之和

range[i]+=range[i-1];

}

//至此，range中存放的是相应键值应该出现的位置

int length=vec.size();

for(int i=length-1;i>=0;--i)        //注意一个小细节，统计时最正序的，这里是逆序

{//如果存在相同的键值，为了保持稳定性，后出现的应该还是位于后面

//如果正序，则先出现的会放置到后面，因此不再稳定

objVec[range[vec[i]]]=vec[i];  //将键值放到目标位置

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. 设置一个定量的数组当作空桶子。

2. 寻访序列，并且把项目一个一个放到对应的桶子去。

3. 对每个不是空的桶子进行排序。

4. 从不是空的桶子里把项目再放回原来的序列中。

假设数据分布在[0，100)之间，每个桶内部用链表表示，在数据入桶的同时插入排序，然后把各个桶中的数据合并。

*****************/

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;

}

}

// 基数排序：一种多关键字的排序算法，可用桶排序实现。

int maxbit(int data[], int n) //辅助函数，求数据的最大位数

{

    int maxData = data[0]; ///< 最大数

    /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。

    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; //保存最大的位数

    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) //基数排序

{

    int d = maxbit(data, n);

    int *tmp = new int[n];

    int *count = new int[10]; //计数器

    int i, j, k;

    int radix = 1;

    for(i = 1; i <= d; i++) //进行d次排序

    {

        for(j = 0; j < 10; j++)

            count[j] = 0; //每次分配前清空计数器

        for(j = 0; j < n; j++)

        {

            k = (data[j] / radix) % 10; //统计每个桶中的记录数

            count[k]++;

        }

        for(j = 1; j < 10; j++)

            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶

        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++) //将临时数组的内容复制到data中

            data[j] = tmp[j];

        radix = radix * 10;

    }

    delete []tmp;

    delete []count;

}

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,491评论 5赞 459
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,856评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,745评论 0赞 319
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,196评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,073评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,112评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,531评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,215评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,485评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,578评论 2赞 309
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,356评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,215评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,583评论 3赞 299
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,898评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,174评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,497评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,697评论 2赞 335

推荐阅读更多精彩内容

  • 七叔的龌龊事（一）
    七叔爱钱，也爱女人，七叔和他的父亲一样，娶了很多老婆，寿命也足够长。 可是，七叔的父亲，也就是我的大爷爷，年轻时候...
    积极人生阅读 1,134评论 2赞 3
  • 记忆，蕴藏在书笺一隅
    流年的碎念，落寞了空灵的眼眸，光阴的流逝，镌刻在眉宇之间。曾经的温馨时光，悉心收藏，浅浅的记忆，淡淡的忧伤，轻轻珍...
    古城苍狼阅读 533评论 2赞 11