赞
踩
排序算法 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 数据对象稳定性 |
---|---|---|---|---|
冒泡排序 | O(n2) | O(n2) | O(1) | 稳定 |
选择排序 | O(n2) | O(n2) | O(1) | 数组不稳定、链表稳定 |
插入排序 | O(n2) | O(n2) | O(1) | 稳定 |
快速排序 | O(n*log2n) | O(n2) | O(log2n) | 不稳定 |
堆排序 | O(n*log2n) | O(n*log2n) | O(1) | 不稳定 |
归并排序 | O(n*log2n) | O(n*log2n) | O(n) | 稳定 |
希尔排序 | O(n*log2n) | O(n2) | O(1) | 不稳定 |
计数排序 | O(n + m) | O(n + m) | O(n + m) | 稳定 |
桶排序 | O(n) | O(n) | O(m) | 稳定 |
基数排序 | O(k*n) | O(n2) | 稳定 |
算法思想
动图
代码
void bubbleSort(int* arr, int len) { for (int i=0;i<len-1;i++) { for (int j=0;j<len-i-1;j++) { if(arr[j]>arr[j+1]) { int tmp = arr[j]; arr[j]=arr[j+1]; arr[j+1]=tmp; } } } }
算法思想
动图
代码
void selectionSort(int *arr, int len) { int minIndex = 0; for (int i = 0; i < len; i++) { minIndex=i; for (int j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } }
算法思想
动图
代码
void insertSort(int* arr,int len)
{
for(int i=0;i<len-1;i++)
{
int j=i+1;
while(arr[j]<arr[j-1]&&j>0)
{
int temp = arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
j--;
}
}
}
void quickSort(int *arr, int low, int high) { if (low >= high) // 结束标志 { return; } int first = low; //地位坐标 int last = high; //高位坐标 int key = arr[first]; //设置第一个为基准 while (first < last) { //将比第一个小的移到前面 while (first < last && arr[last] >= key) { last--; } if (first < last) { arr[first++] = arr[last]; } //将比第一个大的移到后面 while (first < last && arr[first] <= key) { first++; } if (first < last) { arr[last--] = arr[first]; } } arr[first] = key; //前半递归 quickSort(arr, low, first - 1); //后半递归 quickSort(arr, first + 1, high); }
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点旳键值或索引总是小于(或大于)它的父节点
在这里插入代码片 #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; }
归并排序是建立在归并操作上的一种有效排序算法。该算法是采用分治法(divide and conquer)的一个非常典型的应用。将以有序的子序合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序。
算法思想
动图
代码
void print(int a[], int n){ for(int j= 0; j<n; j++){ cout<<a[j] <<" "; } cout<<endl; } //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n] void Merge(ElemType *r,ElemType *rf, int i, int m, int n) { int j,k; for(j=m+1,k=i; i<=m && j <=n ; ++k){ if(r[j] < r[i]) rf[k] = r[j++]; else rf[k] = r[i++]; } while(i <= m) rf[k++] = r[i++]; while(j <= n) rf[k++] = r[j++]; print(rf,n+1); } void MergeSort(ElemType *r, ElemType *rf, int lenght) { int len = 1; ElemType *q = r ; ElemType *tmp ; while(len < lenght) { int s = len; len = 2 * s ; int i = 0; while(i+ len <lenght){ Merge(q, rf, i, i+ s-1, i+ len-1 ); //对等长的两个子表合并 i = i+ len; } if(i + s < lenght){ Merge(q, rf, i, i+ s -1, lenght -1); //对不等长的两个子表合并 } tmp = q; q = rf; rf = tmp; //交换q,rf,以保证下一趟归并时,仍从q 归并到rf } } int main(){ int a[10] = {2,3,4,5,15,19,26,27,36,38,44,46,47,48,50}; int b[10]; MergeSort(a, b, 15); print(b,15); cout<<"结果:"; print(a,10); }
希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非常稳定的排序算法。
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 位。计数排序基于一个假设,待排序数列的所有数均为整数,且出现在(0,k)的区间之内,如果 k(待排序数组的最大值)过大则会引起较大的空间复杂度,一般是用来排序 0 到 100 之间的数字的最好的算法,但是它不适合按字母顺序排序人名。计数排序不是比较排序,排序的速度快于任何比较排序算法。
思想
动图
代码
#include <iostream> #include <vector> #include <algorithm> using namespace std; // 计数排序 void CountSort(vector<int>& vecRaw, vector<int>& vecObj) { // 确保待排序容器非空 if (vecRaw.size() == 0) return; // 使用 vecRaw 的最大值 + 1 作为计数容器 countVec 的大小 int vecCountLength = (*max_element(begin(vecRaw), end(vecRaw))) + 1; vector<int> vecCount(vecCountLength, 0); // 统计每个键值出现的次数 for (int i = 0; i < vecRaw.size(); i++) vecCount[vecRaw[i]]++; // 后面的键值出现的位置为前面所有键值出现的次数之和 for (int i = 1; i < vecCountLength; i++) vecCount[i] += vecCount[i - 1]; // 将键值放到目标位置 for (int i = vecRaw.size(); i > 0; i--) // 此处逆序是为了保持相同键值的稳定性 vecObj[--vecCount[vecRaw[i - 1]]] = vecRaw[i - 1]; } int main() { vector<int> vecRaw = { 0,5,7,9,6,3,4,5,2,8,6,9,2,1 }; vector<int> vecObj(vecRaw.size(), 0); CountSort(vecRaw, vecObj); for (int i = 0; i < vecObj.size(); ++i) cout << vecObj[i] << " "; cout << endl; return 0; }
思想
动图
代码
function bucketSort(arr, bucketSize) { if (arr.length === 0) { return arr; } var i; var minValue = arr[0]; var maxValue = arr[0]; for (i = 1; i < arr.length; i++) { if (arr[i] < minValue) { minValue = arr[i]; // 输入数据的最小值 } else if (arr[i] > maxValue) { maxValue = arr[i]; // 输入数据的最大值 } } // 桶的初始化 var DEFAULT_BUCKET_SIZE = 5; // 设置桶的默认数量为5 bucketSize = bucketSize || DEFAULT_BUCKET_SIZE; var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; var buckets = new Array(bucketCount); for (i = 0; i < buckets.length; i++) { buckets[i] = []; } // 利用映射函数将数据分配到各个桶中 for (i = 0; i < arr.length; i++) { buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]); } arr.length = 0; for (i = 0; i < buckets.length; i++) { insertionSort(buckets[i]); // 对每个桶进行排序,这里使用了插入排序 for (var j = 0; j < buckets[i].length; j++) { arr.push(buckets[i][j]); } } return arr; }
算法思路
动图
代码
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; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。