排序算法合集-创新互联
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
using namespace std;
//直接插入排序
//思路：保留第一个，取第二个和第一个进行比较，如果第二个大于第一个直接插入数组第二个位置，否则
//将第一个向后移动一位，将第二个数据插入第一个位置，再取第三个数据与第二个进行比较以此类推……
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--;//调试一下你就知道怎么回事 } 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++)//从数组第gap个元素开始 // if (a[j] < a[j - gap])//每个元素与自己组内的数据进行直接插入排序 // { // 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; // } // //} //堆排 //向下调整 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;//保存最小的数 for (int j = i+1; j < size; j++)//j=i+1 ？因为前面已经有序，所以不用送1开始而是从1+i开始的； { if (a[j] < a[index]) { index = j;//保存下最小的数的下标 } } if (index != i)//排之前已经是一个序列，所以需要进行交换。 { int tmp = a[index]; a[index] = a[i]; a[i] = tmp; } } } //选择排序的优化 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++)//一次循环找出其中的大值和最小值, { 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); } } //快速排序之挖坑填数 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); } } //优化快速排序 //快速排序的优化-三数取中法 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)//使两个数组有序然后合并 { 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;//将数列分成两半，再将每一半排序 _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; } //计数排序 //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; } //基数排序 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); //获取大位数 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); //统计0-9号桶中共有多少个数据 for (size_t i = 0; i < size; ++i) { int num = (a[i] / digit) % 10; //每个数字模10，取余数，即为个位数字的值，存入相应的位置，个数加1 count[num]++; } //计算个数为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]; } //将桶中的数据拷贝回去 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; } 创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
文章标题：排序算法合集-创新互联
分享URL：http://pwwzsj.com/article/djjsje.html
