#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
using namespace std;
//直接插入排序
//思路：保留第一個，取第二個和第一個進行比較，如果第二個大于第一個直接插入數(shù)組第二個位置，否則
//將第一個向后移動一位，將第二個數(shù)據(jù)插入第一個位置，再取第三個數(shù)據(jù)與第二個進行比較以此類推……
void Insertsort(int *a, size_t size)
{
assert(a);
for (size_t i = 1; i < size; i++)
{
int index = i;
int temp = a[index];
int end = index - 1;
while (end >= 0 && temp { a[end+1] = a[end];//向后移動； end--;//調(diào)試一下你就知道怎么回事 } a[end+1] = temp;//插入 } } //希爾排序 void ShellSort(int *a, size_t size) { assert(a); int gap = (size / 3) + 1; while (gap >0) { for (int i = gap; i < size; i++) { int index = i; int tmp = a[index]; int end = index - gap; while (end >= 0 && tmp < a[end]) { a[end + gap] = a[end]; end -= gap; } a[end + gap] = tmp; } gap /=3; } } //void ShellSort(int a[], int n) //{ // int j, gap; // gap = n/2; // while (gap > 0) // { // //for (gap = n / 2; gap > 0; gap /= 2) // for (j = gap; j < n; j++)//從數(shù)組第gap個元素開始 // if (a[j] < a[j - gap])//每個元素與自己組內(nèi)的數(shù)據(jù)進行直接插入排序 // { // int temp = a[j]; // int k = j - gap; // while (k >= 0 && a[k] > temp) // { // a[k + gap] = a[k]; // k -= gap; // } // a[k + gap] = temp; // } // gap /= 2; // } // //} //堆排 //向下調(diào)整 void AdjustDown(int *a, size_t size, int root) { int child = 2 * root + 1; while (child < size) { if (child + 1 < size&&a[child + 1] > a[child]) { ++child; } if (a[child] > a[root]) { swap(a[child], a[root]); root = child; child = 2 * root + 1; } else { break; } } } void HeapSort(int *a, size_t size) { assert(a); for (int i = (size - 2) / 2; i >= 0; i--) { AdjustDown(a, size, i); } for (size_t i = 0; i < size; ++i) { swap(a[0], a[size -1- i]); AdjustDown(a, size -1- i, 0); } } //選擇排序 void SelectionSort(int*a, size_t size) { for (int i = 0; i < size; i++) { int index=i;//保存最小的數(shù) for (int j = i+1; j < size; j++)//j=i+1 ？因為前面已經(jīng)有序，所以不用送1開始而是從1+i開始的； { if (a[j] < a[index]) { index = j;//保存下最小的數(shù)的下標 } } if (index != i)//排之前已經(jīng)是一個序列，所以需要進行交換。 { int tmp = a[index]; a[index] = a[i]; a[i] = tmp; } } } //選擇排序的優(yōu)化 void SelectSort(int *a, size_t size) { int left = 0; int right = size - 1; for (; left < right; left++, right--) { int max = left; int min = right; for (int i = left; i<=right;i++)//一次循環(huán)找出其中的大值和最小值, { if (a[min]>a[i]) { min = i; } else if (a[max] < a[i]) { max = i; } } if (left != min) { int temp = a[min]; a[min] = a[left]; a[left] = temp; if (max == left) { max = min; } } if (right != max) { int tmp = a[max]; a[max] = a[right]; a[right] = tmp; if (min == right) { min = max; } } } } //冒泡排序 void BubbleSort(int *a, size_t size) { for (int i = 1; i < size; i++) { for (int j = 0; j < size-i; j++) { if (a[j]>a[j + 1]) { int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp; } } } } //快速排序 int PartSort(int *a, int left,int right) { int MidOfThree(int *a, int left, int right); int begin = left; int end = right-1; int key = MidOfThree(a,left,right); while (begin < end) { while (begin < end && a[begin] <= key) { ++begin; } while (end > begin && a[end] >= key) { --end; } swap(a[begin], a[end]); } if (a[begin]>a[right]) { swap(a[begin], a[right]); return begin; } else { return right; } } void QuickSort(int*a,int left,int right) { assert(a); if (left < right) { int boundary = PartSort(a, left, right); QuickSort(a, left, boundary - 1); QuickSort(a, boundary + 1, right); } } //快速排序之挖坑填數(shù) void QuickSort1(int*a, int left, int right) { assert(a); if (left < right) { int begin = left; int end = right; int key = a[left]; while (begin < end) { while (begin < end&&a[end] >= key) { --end; } a[begin] = a[end]; while (begin < end&&a[begin] <= key) { ++begin; } a[end] = a[begin]; } a[begin] = key; QuickSort1(a, left, begin - 1); QuickSort1(a, begin + 1, right); } } //優(yōu)化快速排序 //快速排序的優(yōu)化-三數(shù)取中法 int MidOfThree(int *a, int left, int right) { int mid = left + (right - left) / 2; if (a[mid] < a[left]) { swap(a[mid], a[left]); } if (a[left]>a[right]) { swap(a[left], a[right]); } if (a[mid] > a[right]) { swap(a[mid], a[right]); } return a[mid]; //a[left] } //歸并排序法 //{begin.....mid,mid+1.....end} void MergeArray(int *a, int begin, int mid, int end, int*tmp)//使兩個數(shù)組有序然后合并 { int i = begin; int m = mid; int j = mid + 1; int k = end; int n = 0; while (i <= m && k >= j) { if (a[i] <= a[j]) { tmp[n++] = a[i++]; } else { tmp[n++] = a[j++]; } } while (i <= m) { tmp[n++] = a[i++]; } while (j <= k) { tmp[n++] = a[j++]; } for (int i = 0; i < n; i++) { a[begin+i] = tmp[i]; } } void _MergeSort(int *a, int left, int right,int *tmp) { if (left < right) { int mid = left + (right - left) / 2;//將數(shù)列分成兩半，再將每一半排序 _MergeSort(a, left, mid, tmp); //有點像將兩個有序的單鏈表合并后依然有序 _MergeSort(a, mid + 1, right, tmp); MergeArray(a, left, mid, right, tmp); } } void MergeSort(int *a, size_t size) { int *tmp = new int[size]; if (tmp != NULL) { _MergeSort(a, 0, size - 1, tmp); } delete[]tmp; } //計數(shù)排序 //int a[10] = { 2, 0, 4, 9, 3, 6, 8, 7, 1, 5 }; void CountSort(int *a, size_t size) { assert(a); int max = a[0]; int min = a[0]; for (size_t i = 0; i < size; i++) { if (a[i]>max) { max = a[i]; } if (a[i] < min) { min = a[i]; } } int range = max - min + 1; int *countarray = new int[range]; memset(countarray, 0, sizeof(int)*range); for (size_t i = 0; i < size; i++) { countarray[a[i] - min]++; } size_t index = 0; for (int i = 0; i <= range; i++) { while (countarray[i]-->0) { a[index++] = min + i; } } //delete[] countarray; //countarray = NULL; } //基數(shù)排序 int GetMaxDigit(int *a, size_t size) { int digit = 1; int max = 10; for (size_t i = 0; i < size; i++) { while (a[i]>=max) { ++digit; max *= 10; } } return digit; } void DigitSortLSD(int* a, size_t size) { assert(a); int MaxBit = GetMaxDigit(a, size); //獲取大位數(shù) int* bucket = new int[size]; //為bucket開辟空間 int count[10]; int start[10]; int bit = 1; int digit = 1; while (bit <= MaxBit) { memset(count, 0, sizeof(int)* 10); memset(start, 0, sizeof(int)* 10); //統(tǒng)計0-9號桶中共有多少個數(shù)據(jù) for (size_t i = 0; i < size; ++i) { int num = (a[i] / digit) % 10; //每個數(shù)字模10，取余數(shù)，即為個位數(shù)字的值，存入相應(yīng)的位置，個數(shù)加1 count[num]++; } //計算個數(shù)為0-9 的在桶里的起始位置 start[0] = 0; for (size_t i = 1; i < size; ++i) { start[i] = start[i - 1] + count[i - 1]; } for (size_t i = 0; i < size; ++i) { int num = a[i] % 10; bucket[start[num]++] = a[i]; } //將桶中的數(shù)據(jù)拷貝回去 memcpy(a, bucket, sizeof(int)* 10); digit *= 10; ++bit; } } void Test() { int a[10] = { 2, 3, 1, 4, 5, 6, 9, 7, 8, 0 }; Insertsort(a, 10); for (int i = 0; i < 10; i++) { cout << a[i] << " "; } cout << endl; } void Test1() { int a[10] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 }; ShellSort(a, 10); for (int i = 0; i < 10; i++) { cout << a[i] << " "; } cout << endl; } void Test2() { int a[10] = { 4, 5, 1, 2, 3, 6, 9, 0, 8, 7 }; HeapSort(a, 10); for (int i = 0; i < 10; i++) { cout << a[i] << " "; } cout << endl; } void Test3() { int a[10] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 }; SelectSort(a, 10); for (int i = 0; i < 10; i++) { cout << a[i] << " "; } cout << endl; } void Test4() { int a[10] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 }; SelectionSort(a, 10); for (int i = 0; i < 10; i++) { cout << a[i] << " "; } cout << endl; } void Test5() { int a[10] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 }; BubbleSort(a,10); for (int i = 0; i < 10; i++) { cout << a[i] << " "; } cout << endl; } void Test6() { int a[10] = { 2, 0, 4, 9, 3, 6, 8, 7, 1, 5 }; QuickSort(a, 0, 9); for (int i = 0; i < 10; i++) { cout << a[i] << " "; } cout << endl; } void Test7() { int a[10] = { 2, 0, 4, 9, 3, 6, 8, 7, 1, 5 }; MergeSort(a,10); for (int i = 0; i < 10; i++) { cout << a[i] << " "; } cout << endl; } void Test8() { int a[10] = { 2, 0, 4, 9, 3, 6, 3, 3, 1, 5 }; CountSort(a, 10); for (int i = 0; i < 10; i++) { cout << a[i] << " "; } cout << endl; } void Test9() { int a[10] = { 2, 0, 4, 9, 3, 6, 8, 7, 1, 5 }; DigitSortLSD(a, 10); for (int i = 0; i < 10; i++) { cout << a[i] << " "; } cout << endl; } int main() { Test(); Test1(); Test2(); Test4(); Test5(); Test6(); Test7(); Test8(); Test9(); system("pause"); return 0; } 創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準確進行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。
分享標題：排序算法合集-創(chuàng)新互聯(lián)
本文網(wǎng)址：http://weahome.cn/article/djjsje.html
重慶分公司
重慶分公司
