# 数据结构之排序

## sort algorithm in Data structure

Posted by xuepro on February 4, 2019

typedef int T;

//#define C_plus_plus

#ifdef  C_plus_plus

#include <iostream>

using namespace std;

#else

#include <stdio.h>

#endif

void print(T arr[], int n) {

#ifdef  C_plus_plus

for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;

#else

for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");

#endif

}

void insert_sort(T a[],int n) {
for (int i = 1; i < n; i++) {
//[0,...,i-1],a[i]
if (a[i] < a[i - 1]) {
T t = a[i];
a[i] = a[i - 1];
int j;
for (j = i - 2; j >= 0 && t < a[j];j--) {
a[j + 1] = a[j];
}
a[j + 1] = t;
}
}
}

void binary_insert_sort(T a[], int n) {
int i, j, l, h, m; T t;
for (i = 1; i < n; ++i) {
t = a[i]; /* 将a[i]暂存到a[0] */

l = 0; h = i - 1;
while (l <= h) {
/*在a[l...h]中折半查找插入的位置*/

m = (l + h) / 2; /* 折半 */

if (t < a[m])
h = m - 1; /* 插入点在低半区*/

else l = m + 1; /* 插入点在高半区*/

}
for (j = i - 1; j >= h + 1; --j)
a[j + 1] = a[j]; /* 记录后移 */

a[h + 1] = t; /* 插入*/

}
}

void shell_pass(T a[], int n, int d) {
int i, j; T t;
for (i = d; i < n; i++)
if (a[i] < a[i - d]){    //i比i-d小

t = a[i];    //用t先保存a[i]的值

a[i] = a[i - d];   //a[i-d]后移一个单元

//从i-2*d开始，往左扫描，直到找到一个<=t的

for (j = i - 2 * d; j >= 0 && (t < a[j]); j -= d)
a[j + d] = a[j];       //每个元素后移

a[j + d] = t;    //最后把t写入j+1位置
}
}

void shell_sort(T a[], int n) {
int ds[] = { 7,5,3,1 };
for (int i = 0; i < 4; i++)
shell_pass(a, n, ds[i]);
}

void swap(int  *x, int *y) {
int t = *x;  //t  =a[j];

*x = *y;     //a[j] = a[j+1];

*y = t;
}

void bubble_sort(T a[], int n) {
for (int i = n - 1; i > 0; i--) {
int swaped = 0;
for (int j = 0; j < i; j++)
if (a[j] > a[j + 1]) {
swap(&a[j], &a[j + 1]);
swaped = 1;
}
if (swaped == 0) break;
print(a, i+1);
}
}

void select_sort(T data[], int n) {
for (int i = 0; i < n - 1; i++) {
// 找a[i..n-1]最小值位置IndMin

int IndMin = i;
for (int j = i + 1; j < n; j++)
if (data[j] < data[IndMin])
IndMin = j;

// 把IndMin和i作交换

if (IndMin != i)
swap(&data[IndMin], &data[i]);

//print(data,n);

print(data, i+1);
}
}

void merge(T data[], T out[], int s, int M, int N) {
int i = s, j = M + 1, k = s;

//1.两个序列都还有数据

while (i <= M && j <= N)
if (data[i] <= data[j])
out[k++] = data[i++];
else
out[k++] = data[j++];

//2.序列剩余数据依次写入目标序列

while (i <= M)
out[k++] = data[i++];
while (j <= N)
out[k++] = data[j++];
}

void test_merge() {
T arr[] = { 8,21,25,25,49,62,72,93,  16,37,54 };
int s = 0, M = 7, N = 10;
T B[11];
merge(arr, B, s, M, N);
print(B, 11);

}
void copy(T B[], T A[], int n) {
for (int i = 0; i < n; i++)
A[i] = B[i];
}

T min(T a, T b) {
return a < b ? a : b;
}

void merge_sort_iter(T A[], T B[], int n) {
for (int width = 1; width < n; width *= 2) {
for (int i = 0; i < n; i = i + 2 * width)
merge(A, B, i, min(i + width - 1, n - 1), min(i + 2 * width - 1, n - 1));
copy(B, A, n);
}
}

void copy(T B[], T A[], int s,int t) {
for (int i = s; i <= t; i++)
A[i] = B[i];
}
void merge_sort(T A[], T B[], int s, int t) {
if (t == s) { B[s] = A[s]; return; }
merge_sort(A, B, s, (s + t) / 2);
merge_sort(A, B, (s + t) / 2 + 1, t);
merge(B, A, s, (s + t) / 2, t);
copy(A, B, s, t);
}

//----------快速排序-----------
int Partition(T a[], int L, int H) {
T  t = a[L];    //把最左元素当作基准

while (L < H) {
//H向左，直到遇见比pivot小的

while (L < H && !(a[H] < t))
H--;
a[L] = a[H];

//L向右，直到遇见比pivot大的

while (L < H && a[L] < t)
L++;
a[H] = a[L];
}
a[L] = t;
return L;
}

void QSort(T a[], int L, int H) {
if (L < H) {    //待排序数列长度大于1

int pivotloc = Partition(a, L, H);

//对左子序列进行快速排序

QSort(a, L, pivotloc - 1);

//对右子序列进行快速排序

QSort(a, pivotloc + 1, H);
}
}

int main() {
T arr[] = { 38,69,45,97,76,13,27 };
int n = 7;
print(arr, n);
//insert_sort(arr, n);

//binary_insert_sort(arr, n);

//shell_sort(arr, n);

//bubble_sort(arr, n);

//select_sort(arr, n);

//T B[7];

//test_merge(); return 0;

//merge_sort_iter(arr, B, n);

//print(B, n);

//merge_sort(arr, B, 0, n - 1);

//print(B, n);

QSort(arr, 0, n - 1);

print(arr, n);

}