14种排序

冒泡排序：

void bubble_sort(int arr[],int left, int right) {
for (int i = left; i < right; i++) {
for (int j = 0; j < right-i; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j], arr[j+1]);
}
}
}
}

选择排序

void select_sort(int arr[], int left, int right) {
for (int i = left; i < right; i++) {
for (int j = i; j <= right ; j++) {
if (arr[i] > arr[j])
swap(arr[i],arr[j]);
}
}
}

插入排序

void insert_sort(int arr[], int left, int right) {
for (int cur = left + 1; cur <= right; cur++) {
int tmp = arr[cur];
int i = cur - 1;
while (i>=left && tmp arr[i + 1] = arr[i];
i--;
}
arr[i+1] = tmp;
}
}

堆排序

完全二叉树

void heapify(int tree[],int n,int i) {
int parent = i, c1 = 2 * i + 1, c2 = 2 * i + 2;
if (tree[parent] < tree[c1]&&c1<=n)
swap(tree[parent], tree[c1]);

if (tree[parent] < tree[c2]&&c2<=n)
swap(tree[parent], tree[c2]);
}

void build_heap(int tree[], int n) {
int node = (n - 1) / 2;
for (int i = node; i >= 0; i--)
heapify(tree, n, i);
}

void heap_sort(int tree[],int n) {
for (int i = n; i >= 0; i--) {
build_heap(tree, i);
/*cout << " 堆：";
for (int j = 0; j <=i; j++) {
cout << tree[j] << " ";
}*/
swap(tree[0], tree[i]);
}

 归并排序

void merge(int arr[], int L, int M, int R) {
int left_size = M-L+1,right_size = R-M;
int left[INF], right[INF];
int i = 0, j = 0, k = L;
for (int m = 0; m < left_size; m++) {
left[m] = arr[L + m];
}
for (int m = 0; m < right_size; m++) {
right[m] = arr[M + 1 + m];
}
while (i < left_size && j < right_size) {
if (left[i] < right[j]) {
arr[k] = left[i];
k++;
i++;
}else{
arr[k] = right[j];
k++;
j++;
}
}
while (i < left_size) {
arr[k] = left[i];
k++;
i++;
}
while (j < right_size) {
arr[k] = right[j];
k++;
j++;
}

void merge_sort(int arr[], int L, int R) {
int M = (R + L) / 2;
if (R <= L )return;
merge_sort(arr, L, M);
merge_sort(arr, M+1, R);
merge(arr, L, M, R);
}

二分插入排序

int binary_search(int arr[], int left, int right,int value) {
while (abs(left - right) > 1) {
int mid = (left + right) >> 1;
//cout << left << " " << right << endl;
if (value <= arr[mid])
right = mid;
else
left= mid + 1;
}
return left;
}
void binary_sort(int arr[], int left, int right) {
for (int cur = left + 1; cur <= right; cur++) {
int tmp = arr[cur];
int i = cur - 1;
int idx=binary_search(arr, left, cur-1, tmp);
for (int j=cur; j > idx; j--) {
arr[j] = arr[j - 1];
}
arr[idx] = tmp;
}
}

 希尔排序

void shell_sort(int arr[], int left, int right,int N) {
for (int gap = N/2; gap >= 1; gap = gap / 2) {
for (int cur = left + gap; cur <= right; cur+=gap) {
int tmp = arr[cur];
int i = cur - gap;
while (i >= left && tmp < arr[i]) {
arr[i+gap] = arr[i];
i-=gap;
}
arr[i+gap] = tmp;
}
}
}

鸡尾酒排序

void cocktail_sort(int arr[], int left, int right) {
int i = left, j = right;
while (i < j) {
for (int k = i; k < j; k++) {
if (arr[k] > arr[k + 1])
swap(arr[k], arr[k + 1]);
}
j--;
for (int k = j; k > i; k--) {
if (arr[k] < arr[k - 1])
swap(arr[k], arr[k - 1]);
}
i++;
}
}

 计数排序（适用于量特别大，但是范围比较小（年龄排序、高考名次））