"桶"排序
简单"桶"排序,n个数需要n+1个变量申明,若n的较大造成所占空间过大,变量存储的值是该数所出现过的次数.
时间复杂度为O(M+N)
冒泡排序
n个数进行n-1趟操作,每趟比较直到最后一个未归位的数.
时间复杂度为O(N^2).
void bubbleSort(int data[], int n) {
for (int i = 1; i <= n-1; ++i) {
for(int j = 1; j <= n-i; j++) {
if (data[j] < data[j+1]) {
int temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
}
}
}
}
快速排序
设定基数,进行跳跃式互换位置.两端同时向中间比较,右边找比基数小的,左边找比基数大的,然后进行互换,直至相遇将基数位置放中;然后重复递归原基数的左边和右边.
平均时间复杂度为O(NlogN)
void quickSort(int data[], int left, int right) {
if (left > right)
{
return;
}
int i = left;
int j = right;
int base = data[left];
while(i != j) {
while(a[j] > base && i > j ) {
j--;
}
while(a[i] < base && i > j) {
i++;
}
if (i < j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
// 将基数归位于中间位置
a[left] = a[i];
a[i] = base;
quickSort(left, i - 1); // 递归左边
quickSort(i + 1, right); // 递归右边
}
小结
在"桶"排序, 冒泡排序, 快速排序以上这三种中效率最高的是快速排序.
