数据结构之排序

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);

}