C++如何实现九种排序
这篇文章主要讲解了C++如何实现九种排序,内容清晰明了,对此有兴趣的小伙伴可以学习一下,相信大家阅读完之后会有帮助。
创新互联公司专注于铜鼓网站建设服务及定制,我们拥有丰富的企业做网站经验。 热诚为您提供铜鼓营销型网站建设,铜鼓网站制作、铜鼓网页设计、铜鼓网站官网定制、微信小程序定制开发服务,打造铜鼓网络公司原创品牌,更为您提供铜鼓网站排名全网营销落地服务。
直接插入排序
void InsertSort(int r[]) { int n = sizeof(r) / sizeof(r[0]); for(int i = 1; i < n; ++i) { for(int j = i - 1; j >= 0; --j) { if(r[j+1] < r[j]) { int s = r[j+1]; r[j+1] = r[j]; r[j] = s; } } } }
折半插入排序
void BinInsertSort(int r[]) { int n = sizeof(r) / sizeof(r[0]); for(int i = 1; i < n; ++i) { int s = r[i]; int low = 0; int high = i - 1; while(low <= high) { int mid = (low + high) / 2; //mid位置为要找的数 if(s < r[mid]) high = mid - 1; else low = mid + 1; } for(int j = i - 1; j >= high + 1; --j) //high+1即mid,执行数的后移,直到mid的数后移 r[j+1] = r[j]; r[high+1] = s; //mid位置就存放本身 } }
希尔排序
void ShellSort(int r[]) { int n = sizeof(r) / sizeof(r[0]); int step = n / 2; while(step >= 1) { for(int i = step; i < n; ++i) { for(int j = i - step; j >= 0; j -= step) { if(r[j+step] < r[j]) { int s = r[j+step]; r[j+step] = r[j]; r[j] = s; } } } step /= 2; } }
直接选择排序
void SelectSort(int r[]) { int n = sizeof(r) / sizeof(r[0]); for(int i = 0; i < n - 1; ++i) { int samll = i; for(int j = i + 1; j < n; ++j) { if(r[small] > r[j]) samll = j; } if(small != i) { int s = r[i]; r[i] = r[small]; r[small] = s; } } }
堆排序
void HeapAdjust(int r[]; int i; int j) //调整堆 { int child = 2 * i; int s = r[i]; //s临时存放结点数据 while(child <= j) { if(child < j && r[child+1] > r[child]) //比较2个子树 ++child; if(s >= r[child]) //结点与大子树比较 break; r[child/2] = r[child]; //如果大子树比结点大,互换 child = 2 * child; //继续向子树检索 } r[child/2] = s; //结点的数为最大的数 } void HeapSort(int r[]) //建堆 { int n = sizeof(r) / sizeof(r[0]); for(int i = n / 2 - 1; i >= 0; --i) //只有n/2-1前的下标才有子树 { HeapAdjust(r, i, n - 1); //构造大顶堆,结点都比子树大,最后根节点为最大的数 } for(int i = n - 1; i > 0; --i) { //将当前堆顶元素与当前堆尾元素互换,即将最大的数移到末尾 int s = r[0]; r[0] = r[i]; r[i] = s; HeapAdjust(r, 0, i -1); //将剩下的元素继续调整,最后变成由小到大的顺序 } }
冒泡排序
void BubbleSort(int r[]) { int n = sizeof(r) / sizeof(r[0]); for(int i = 0; i < n - 1; ++i) { for(int j = 0; j < n - 1 - i; ++j) { if(r[j] > r[j+1]) { int s = r[j]; r[j] = r[j+1]; r[j+1] = s; } } } }
快速排序
int Partition(int r[], int low, int high) { int pivotkey = r[low]; int i = low; int j = high; while(i < j) { while(i < j && r[j] > pivotkey) //从j往前找,找出第一个比pivotkey小的数 --j; if(i < j) { r[i] = r[j]; ++i; } while(i < j && r[i] < pivotkey) //从i往后找,找出第一个比pivotkey大的数 ++i; if(i < j) { r[j] = r[i]; --j; } } r[j] = pivotkey; //完成最终交换 return j; //返回分界点,前面的数都比pivotkey小,后面的数都比pivokey大 } void QuickSort(int r[], int low, int high) // 传数组、0和长度-1 { if(low < high) { int pivot = Partition(r, low, high); QuickSort(r, low, pivot - 1); //递归,前半部分继续进行快速排序 QuickSort(r, pivot + 1; high); //递归,后半部分继续进行快速排序 } }
归并排序
void copyArray(int source[], int dest[], int len, int first) { int i; int j = first; for(i = 0; i < len; ++i) { dest[j] = source[i]; ++j; } } void merge(int a[], int left, int right) { int begin1 = left; int mid = (left + right) / 2; int begin2 = mid + 1; int newArrayLen = right - left + 1; int *b = (int*)malloc(newArrayLen * sizeof(int)); int k = 0; while(begin1 <= mid && begin2 <= right) //找出2组中比较后小的那个数按顺序放进b空间 { if(a[begin1] <= a[begin2]) b[k++] = a[begin1++]; else b[k++] = a[begin2++]; } //把剩下的数放进b空间 while(begin1 <= mid) b[k++] = a[begin1++]; while(begin2 <= right) b[k++] = a[begin2++]; copyArray(b, a, newArrayLen, left); //把b空间的数写回原数组 free(b); } void MergeSort(int r[], int left, int right) //传数组、0和长度-1 { int i; //至少有两个元素才进行排序 if(left < right) { i = (left + right) / 2; MergeSort(r, left, i); //前半部分递归 MergeSort(r, i + 1, right); //后半部分递归 merge(r, left, right); //10个数的比较顺序为[0,1][0,2][3,4][0,4][5,6][5,7][8,9][5,9][0,9] } }
桶排序
void insert(list&bucket, int val) { auto iter = bucket.begin(); while(iter != bucket.end() && val >= *iter) ++iter; //insert会在iter之前插入数据,这样可以稳定排序 bucket.insert(iter, val); } void BuckdeSort(vector &arr) { int len = arr.size(); if(len <= 1) return; int min = arr[0], max = min; for(int i = 1; i < len; ++i) //找出最小值和最大值 { if(min > arr[i]) min = arr[i]; if(max < arr[i]) max = arr[i]; } int k = 10; //桶的大小 //向上取整,例如[0,9]有10个数,就有(9-0)/k+1=1个桶 int bucketsNum = (max - min) / k + 1; //桶的个数 vector > buckets(bucketsNum); for(int i = 0; i < len; ++i) { int value = arr[i]; //(value-min)/k就是在哪个桶里面 insert(buckets[(value-min)/k], value); //将数据放到各个桶里并排序 } int index = 0; for(int i = 0; i < bucketsNum; ++i) { if(buckets[i].size()) { for(auto &value : buckets[i]) arr[index++] = value; } } }
看完上述内容,是不是对C++如何实现九种排序有进一步的了解,如果还想学习更多内容,欢迎关注创新互联行业资讯频道。
分享文章:C++如何实现九种排序
分享地址:http://scyanting.com/article/gdjgho.html