#include "sort.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
//插入排序
void insert_sort(int A[], int left, int right)
{
int i, j, tmp;
for(i = left+1; i<=right; i++) {
tmp = A[i];
for(j = i; j>left && tmp<A[j-1]; j--) {
A[j] = A[j-1];
}
A[j] = tmp;
// print(A, left, i);
// printf("\n");
}
}
void select_sort(int A[], int left, int right)
{
int i, j, k, tmp;
for(i=1; i<=right-left; i++) {
for(j=0, k=right-i+1, tmp=A[k]; j<=right-i; j++) {
if(A[j]>A[k]) {
tmp = A[j];
k=j;
}
}
if(k!=right-i+1) {
A[k] = A[right-i+1];
A[right-i+1] = tmp;
}
}
}
void bubble_sort(int A[], int left, int right)
{
int i, j, tmp;
int flag = 0;
for(i = 1; i<=right-left; i++) {
flag = 0;
for(j = 0; j<=right-i; j++) {
if(A[j] > A[j+1]) {
flag = 1;
tmp = A[j];
A[j] = A[j+1];
A[j+1] = tmp;
}
}
if(flag == 0) break;
}
}
//希尔排序
//增量序列的一种流行（但是不好）的选择是使用Shell建议的序列：
// h_t=\lfloor N/2\rfloor和h_k = \lfloor h_{k+1}/2\rfloor。
void shell_sort(int A[], int left, int right)
{
int i, j, tmp, increment;
for(increment = (right-left+1)/2; increment>0; increment /= 2) {
for(i = increment; i<=right; i++) {
tmp = A[i];
for(j = i; j>=increment && tmp<A[j-increment]; j -= increment) {
A[j] = A[j-increment];
}
A[j] = tmp;
}
// print(A, left, right);
// printf("\n");
}
}
//堆排序
void heap_sort(int A[], int left, int right);
//归并排序
/*
MERGE-SORT(A, p, r)
1 if p < r
2 q = (p+r)/2
3 MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q+1, r)
5 MERGE(A, p, q, r)
*/
void merge_sort(int A[], int tmparray[], int left, int right)
{
if(left < right) {
int mid = (left+right)/2;
merge_sort(A, tmparray, left, mid);
merge_sort(A, tmparray,mid+1, right);
merge(A, tmparray, left, mid, right);
}
}
void merge(int A[], int tmparray[], int left, int mid, int right)
{
int i = mid+1, pos = left, num = right-left+1;
while(left<=mid && i<=right) {
if(A[left]<=A[i]) {
tmparray[pos++] = A[left++];
} else {
tmparray[pos++] = A[i++];
}
}
while(left<=mid) {
tmparray[pos++] = A[left++];
}
while(i<=right) {
tmparray[pos++] = A[i++];
}
for(i = 0; i<num; i++) {
A[right] = tmparray[right];
right--;
}
// print(A,right+1, right+num);
// printf("\n");
}
//快速排序
int Partition(int A[], int left, int right)
{
//每次选择数组A[left, right]的第一个元素作为主元
int i = left+1, j = right;
int key = A[left];
int tmp = 0;
do{
while(i<=right && A[i]<key){
i++;
}
while(j>=left && A[j]>key){
j--;
}
if(i<j){
tmp = A[i];
A[i]=A[j];
A[j]=tmp;
}
}while(i<j);
A[left]=A[j];
A[j]=key;
return j;//返回主元下标位置
}
void quick_sort(int A[], int left, int right)
{
if(right>left){
int mid = Partition(A, left, right);
quick_sort(A, left, mid-1);
quick_sort(A, mid+1, right);
}
}
//桶排序
void bucket_sort(int A[], int left, int right, int M)
{
int *bucket = (int *)malloc(sizeof(int)*(M+1));
int i, j;
memset(bucket, 0, (M+1)*sizeof(int));
for(i = left; i<=right; i++) {
bucket[A[i]]++;
}
for(i = 0, j = 0; i<=M; i++) {
if(bucket[i]>0) {
A[j] = i;
j++;
}
}
free(bucket);
bucket = NULL;
}
//基数排序
void radix_sort(int A[], int left, int right);
//打印
void print(int A[], int left, int right)
{
int i = left;
while(i<=right) {
printf(" %d's element: %d;", i, A[i]);
i++;
}
}
