1. 冒泡排序
/**
* 冒泡排序
* @param array
* @param len
*/
void bubbleSore(int array[], int len) {
for (int i = 0; i < len - 1; ++i) {
for (int j = 0; j < len - i - 1; ++j) {
if (array[j] > array[j + 1]) {
std::swap(array[j], array[j + 1]);
}
}
}
}
2.選擇排序
/**
* 選擇排序
* @param array
* @param len
*/
void selectSore(int array[], int len) {
for (int i = 0; i < len; ++i) {
int min_index = i;
for (int j = i; j < len; ++j) {
if (array[min_index] > array[j]) {
min_index = j;
}
}
std::swap(array[min_index], array[i]);
}
}
3. 插入排序
/**
* 插入排序啊
*/
void insertSore(int array[], int len) {
int i, j;
for (i = 1; i < len; ++i) {
int tmp = array[i];
for (j = i; j > 0 && array[j - 1] > tmp; --j) {
// if (array[j - 1] > tmp) {
array[j] = array[j - 1];
// } else {
// break;
// }
}
array[j] = tmp;
}
}
4. 希爾排序
/**
* 希爾排序
* @param array
* @param len
*/
void shellSore(int array[], int len) {
int inCount = len / 2;
do {
int i, j, k;
for (i = 0; i < inCount; ++i) {
for (j = i + inCount; j < len; j += inCount) {
int tmp = array[j];
for (k = j; k > i && array[k - inCount] > tmp; k -= inCount) {
array[k] = array[k - inCount];
}
array[k] = tmp;
}
}
inCount /= 2;
} while ((inCount > 0));
}
5. 歸并排序(遞歸實(shí)現(xiàn))
void _merge(int array[], int l, int mid, int r) {
int tmp[r - l + 1];
for (int i = l; i <= r; ++i) {
tmp[i - l] = array[i];
}
int i = l;
int j = mid + 1;
int k = l;
for (; k <= r; ++k) {
if (i > mid) {
array[k] = tmp[j - l];
j++;
} else if (j > r) {
array[k] = tmp[i - l];
i++;
} else if (tmp[i - l] < tmp[j - l]) {
array[k] = tmp[i - l];
i++;
} else {
array[k] = tmp[j - l];
j++;
}
}
}
void _mergeSore(int array[], int l, int r) {
if (l >= r) {
return;
}
int mid = (l + r) >> 1;
_mergeSore(array, l, mid);
_mergeSore(array, mid + 1, r);
_merge(array, l, mid, r);
}
/**
* 歸并排序
* @param array
* @param len
*/
void mergeSore(int array[], int len) {
_mergeSore(array, 0, len - 1);
}
6. 快速排序(遞歸實(shí)現(xiàn))
int _partition(int array[], int l, int r) {
int index = rand() % (r - l + 1) + l;
std::swap(array[l], array[index]);
int v = array[l];
int p = l;
for (int i = l; i <= r; ++i) {
if (array[i] < v) {
std::swap(array[p + 1], array[i]);
p++;
}
}
std::swap(array[l], array[p]);
return p;
}
void _quickSore(int array[], int l, int r) {
if (l >= r) {
return;
}
int p = _partition(array, l, r);
_quickSore(array, l, p - 1);
_quickSore(array, p + 1, r);
}
//快速排序
void quickSore(int array[], int len) {
srand(time(NULL));
_quickSore(array, 0, len - 1);
}
6.1 快排（三路快排）
void _quickSore3way(int array[], int l, int r) {
if (l >= r) {
return;
}
int index = rand() % (r - l + 1) + l;
std::swap(array[l], array[index]);
int v = array[l];
int lt = l;
int gt = r + 1;
int i = l;
while (gt > i) {
if (array[i] > v) {
std::swap(array[gt - 1], array[i]);
gt--;
} else if (array[i] < v) {
std::swap(array[lt + 1], array[i]);
lt++;
i++;
} else {
i++;
}
}
std::swap(array[l], array[lt]);
_quickSore3way(array, l, lt - 1);
_quickSore3way(array, gt, r);
}
//三路快排
void quickSore3way(int array[], int len) {
srand(time(NULL));
_quickSore3way(array, 0, len - 1);
}
7. 堆排序
void adjustmentArray(int array[], int index, int len) {
while (index * 2 + 1 < len) {
int max = 2 * index + 1;
if (max + 1 < len && array[max] < array[max + 1]) {
max = max + 1;
}
if (array[index] > array[max]) {
break;
}
swap(array[index], array[max]);
index = max;
}
}
/**
* 堆排序
* @param array
* @param len
*/
void heapSort(int array[], int len) {
//調(diào)整最大堆
for (int i = (len / 2) - 1; i >= 0; --i) {
adjustmentArray(array, i, len);
}
for (int i = len - 1; i > 0; --i) {
std::swap(array[0], array[i]);
adjustmentArray(array, 0, i);
}
}
