# 数据结构

``````#define M 100
typedef int datatype;
typedef struct node{
datatype r[M+1];
int lengh;
}table;``````

``````#define M 100
typedef int datatype;
typedef struct {
datatype key;
//其他数据...
}sort_record;
typedef struct node{
sort_record r[M+1];
int lengh;
}table;``````

# 插入排序

## 1. 直接插入排序

``````//1.直接插入
void direct_insert_sort(table* tab)
{
int i,j;
for (i = 1;i<tab->lengh;i++)
{
j = i-1;
tab->r[0] = tab->r[i];
while(tab->r[0] < tab->r[j])
{
tab->r[j+1] = tab->r[j];
j = j-1;
}
tab->r[j+1] = tab->r[0];
}
}``````

## 2. 二分插入排序

``````void binary_insert_sort(table* tab)
{
int i,j,left,right,mid;
for(i =1;i<tab->lengh;i++)
{
left = 1;right = i-1;
tab->r[0] = tab->r[i];
while(left <= right)
{
mid = (left + right) /2;
if (tab->r[mid] > tab->r[0]){
right = mid -1;
}
else{
left = mid+1;
}
}
for (j=i-1;j>=left;j--)
{
tab->r[j+1] = tab->r[j];
}
tab->r[left] = tab->r[0];
}
}``````

## 3. 希尔插入排序

``````void shell_sort(table* tab)
{
int i,j,gap;
gap = tab->lengh / 2;
while(gap >= 1)
{
for (i = 1+gap;i<=tab->lengh;i++)
{
j = i -gap;
tab->r[0] = tab->r[i];
while(tab->r[0] < tab->r[j] && j>0)
{
tab->r[j+gap] = tab->r[j];
j = j-gap;
}
tab->r[j +gap] = tab->r[0];
}
gap = gap/2;
}
}``````

# 交换排序

## 4. 冒泡排序

``````//4.冒泡排序
void bubble_sort(table* tab)
{
int i,j,done;
done = 1;
for(i = 1;i<= tab->lengh&&done;i++)
{
done = 0;
for (j = 1;j<= tab->lengh - i;j++)
{
if (tab->r[j] > tab->r[j+1])
{
swap(tab->r[j],tab->r[j+1]);
done = 1;
}
}
}
}``````

## 5. 快速排序

``````//5.快速排序
void quick_sort(table* tab,int left,int right)
{
if (left >= right)
return;
int i,j;
i = left;j = right;
tab->r[0] = tab->r[i];
while(i < j)
{
while(tab->r[i] <= tab->r[j]&&i<j)
j--;
if (i<j){
tab->r[i] = tab->r[j];
i++;
}
while(tab->r[j] >= tab->r[i]&&i<j)
i++;
if (i<j){
tab->r[j] = tab->r[i];
j--;
}
}
tab->r[i] = tab->r[0];
quick_sort(tab,left,i-1);
quick_sort(tab,i+1,right);
}``````

# 选择排序

## 6. 直接选择排序

``````//6.直接选择
void direct_select_sort(table* tab)
{
int i,j,k;
for (i =1;i<=tab->lengh;i++)
{
k = i;
for(j = i+1;j<=tab->lengh;j++)
{
if (tab->r[k] > tab->r[j])
k = j;
}
if (k != i)
{
swap(tab->r[k],tab->r[i]);
}
}
}``````

## 7. 堆排序

``````//7.堆排序
//index表示要调整的节点的下标，n表示堆元素个数。
void shift_heap(table* tab,int index,int n)
{
int i,j,finished = 0;
tab->r[0] = tab->r[index];
i = index; j = 2*i;
while(j<=n && !finished)
{
if (tab->r[j] > tab->r[j+1]&&j<=n)
j++;
if (tab->r[0] <= tab->r[j])
{
finished = 1;
}
else
{
tab->r[i] = tab->r[j];
i = j;
j = 2*i;
}
}
tab->r[i] = tab->r[0];
}
void heap_sort(table* tab)
{
int i;
for (i = tab->lengh/2;i>=1;i--)
{
shift_heap(tab,i,tab->lengh);
}
for (int i = 2;i<tab->lengh;i++)
{
shift_heap(tab,i,tab->lengh);
}
}``````

# 8. 归并排序

``````//8.归并排序
//将tabs中的u-m-v的元素合并到tabg中
void merge(table* tabs,table* tabg,int u,int m,int v)
{
int i,j,k,t;
i = u; j = m +1;
k = u;
while(i<=m && j <= v)
{
if (tabs->r[i] < tabs->r[j])
{
tabg->r[k++] = tabs->r[i];
i++;
}
else
{
tabg->r[k++] = tabs->r[j];
j++;
}
}
if (i<=m)
{
for(t = i;t<=m;t++)
tabg->r[k++] = tabs->r[t];
}
else
{
for(t = i;t<=v;t++)
tabg->r[k++] = tabs->r[t];
}
}
//递归实现
void merge_sort1(table* tabs,table* tabg,int left,int right)
{
if (left>= right)
{
return;
}
int mid = (left+right)/2;
merge_sort1(tabs,tabg,left,mid);
merge_sort1(tabs,tabg,mid+1,right);
merge(tabs,tabg,left,mid,right);
}
//非递归实现
void merge_pass(table* tabs,table* tabg,int len)
{
int i,j,n;
tabg->lengh = n = tabs->lengh;
for(i =1;i<n-2*len+1;i+=2*len)
{
merge(tabs,tabg,i,i+len-1,i+2*len-1);
}

if (i+len-1<n){
merge(tabs,tabg,i,i+len-1,n);
}
else{
for(j=i;j<=n;j++){
tabg->r[j] = tabs->r[j];
}
}
}
void merge_sort(table* tab)
{
int len;
table tmp;
len =1;
while(len<tab->lengh)
{
merge_pass(tab,&tmp,len);
len = 2*len;
merge_pass(&tmp,tab,len);
len = 2*len;
}
}
``````

# 9. 桶排序

``````/* * 桶排序 * tab -- 排序结构 * max --待排序结构中最大范围[0,max) */
void bucket_sort(table* tab,int max)
{
int i,j;
int* bucket;
if (tab == NULL || tab->lengh > max || max < 1)
return;
if ((bucket = (int*)malloc(sizeof(int)*max)) == NULL)
return;
memset(bucket,0,max*sizeof(int));
//1.计数
for (i = 1;i<tab->lengh;i++)
{
bucket[tab->r[i]]++;
}
//2.排序
for(i = 1,j = 1;i < max;i++)
{
while(bucket[i]-- != 0)
tab->r[j++] = i;
}
free(bucket);
}``````