# 部分排序算法c语言实现

algorithm Repository :C语言实现部分排序算法，代码质量较高，其实现类似于库函数

sorting and searching algorithms :点击左边的链接即可查看整份文档

sort.c:

```/* to compiler the program, use: gcc -o sort sort.c misc.c -g -Wall
/* insert sort */
#include <stdio.h>
#include <stdlib.h>
#include "misc.h"

int insertSort(int a[], int n);
int shellSortSh(int a[], int n);
int shellSortHi(int a[], int n);
int shellSortKn(int a[], int n);
int bubSort(int a[], int n);
int selectSort(int a[], int n);
int median3(int a[], int n);
int quickSort(int a[], int n);
int heapify(int a[],int i, int n);
int heapSort(int a[], int n);
int mergeArray(int a[],int splitIndex,int n);
int mergeSort(int a[], int n);
/*
void testMedian3()
{
int a[3] = {3,2,1};
int len = ARRLEN(a);

median3(a,len);
printArray(a,len);
}*/
int main(void)
{
int a[] = {8,1,4,9,6,3,5,2,7,0};
/*  int a[] = {5,7,3,8};*/
int len = ARRLEN(a);
/*  testSort(a,len,insertSort);*/
/*  testSort(a,len,shellSortKn);*/
testSort(a,len,mergeSort);
/*  testMedian3();*/
return 0;
}
int insertSort(int a[], int n)
{
int i,j;
int tmp;
for(i = 0; i < n; i++)
{
tmp = a[i];
for(j = i; j > 0 && a[j-1] > tmp; --j)
a[j] = a[j-1];
a[j] = tmp;
/*      printArray(a,n);*/
}
return 0;
}
/* the origin shell sort by Shell using increment sequence
of n/2,n/4 ... 1 */
int shellSortSh(int a[], int n)
{
int i,j;
int inc;
int tmp;

for(inc = n/2; inc > 0; inc /= 2)
for(i = inc; i <n; i++)
{
tmp = a[i];
for(j = i; j >= inc && tmp < a[j-inc]; j -= inc)
a[j] = a[j-inc];
a[j] = tmp;
printArray(a,n);
}
return 0;
}
/* shell sort by Hibbard's sequence:
2^k-1,...,7,3,1 */
int shellSortHi(int a[],int n)
{
int i,j;
int inc;
int tmp;
for(inc = 1; inc < n/2; inc = 2*inc+1) ;
for( ; inc > 0; inc /= 2)
for(i = inc; i <n; i++)
{
tmp = a[i];
for(j = i; j >= inc && tmp < a[j-inc]; j -= inc)
a[j] = a[j-inc];
a[j] = tmp;
printArray(a,n);
}
return 0;
}
/* Shell sort using knuth's sequence:
(3^k-1)/2,...,13,4,1 */
int shellSortKn(int a[], int n)
{
int i,j;
int inc;
int tmp;
for(inc = 1; inc < n/3; inc = 3*inc+1) ;
for( ; inc > 0; inc /= 3)
for(i = inc; i <n; i++)
{
tmp = a[i];
for(j = i; j >= inc && tmp < a[j-inc]; j -= inc)
a[j] = a[j-inc];
a[j] = tmp;
printArray(a,n);
}
return 0;
}
/*for shell sort there is also a Sedgewick's sequence:
1,5,19,41,...
which can be constructed by:
1,19,104,505,...,9(4^k-2^k)+1, k=0,1,2,3,...
5,41,209,929,...,(2^(k+2))*(2^(k+2)-3)+1, k = 0,1,2,3,.. */

/*bubble sort */
int bubSort(int a[], int n)
{
int i,j,tmp;
for(i = n-1; i >= 0; --i)
for(j = 0;  j < i; j++)
if(a[j] >a[j+1])
{
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
return 0;
}
/* select sort */
int selectSort(int a[], int n)
{
int i,j;
int minIndex,minNum;
for(i = 0; i < n; i++)
{
minIndex = i;
minNum = a[i];
for(j = i+1; j < n; j++)
if(a[j] < minNum)
{
minIndex = j;
minNum = a[j];
}
a[minIndex] = a[i];
a[i] = minNum;
}
return 0;
}
/* partition function to find a element to cut an array to two pieces */
/* This function is used by quick sort function */
int median3(int a[], int n)
{
int mid = n/2-1;

/* the following three sentences make sure that
a[0] <= a[mid] <= a[n-1] */
if(a[0] > a[mid])
swap(&a[0],&a[mid]);
if(a[0] > a[n-1])
swap(&a[0],&a[n-1]);
if(a[mid] > a[n-1])
swap(&a[mid],&a[n-1]);

/* exchange elemments to set the pivot at the beginning of array */
swap(&a[0],&a[mid]);
return a[0];
}
/* quick sort */
int quickSort(int a[], int n)
{
int low = 1, high = n-1;
int pivot;
printArray(a,n);
if(n <= 3)
{
insertSort(a,n);
return 0;
}
pivot = median3(a,n);
while(low < high)
{
while(a[low] < pivot) low++;
while(a[high] > pivot) high--;
if(low < high)
swap(&a[low],&a[high]);
else
break;
/*      printArray(a,10);*/
}
swap(&a[0],&a[low-1]);
quickSort(a,low-1);
quickSort(a+low,n-low);
return 0;
}
int heapify(int a[], int i, int n)
{
int maxIndex = i;
int lChild = 2*i+1,rChild = lChild+1;
if(lChild < n && a[lChild] > a[maxIndex])
maxIndex = lChild;
if(rChild < n && a[rChild] > a[maxIndex])
maxIndex = rChild;
if(maxIndex != i)
{
swap(&a[maxIndex],&a[i]);
heapify(a,maxIndex,n);
}
return 0;
}
int heapSort(int a[], int n)
{
int i;
for(i = (n-1)/2; i >= 0; i--)
heapify(a,i,n);
for(i = n-1; i >0; i--)
{
swap(&a[i],&a[0]);
heapify(a,0,--n);
}
return 0;
}
int mergeArray(int a[], int splitIndex, int n)
{
int *tmpArray = malloc(n*sizeof(int));
int i ,left,right;
i = left= 0;right = splitIndex;
while(left < splitIndex && right < n)
{
if(a[left] <= a[right])
tmpArray[i++] = a[left++];
else
tmpArray[i++] = a[right++];
}
while(left < splitIndex)
tmpArray[i++] = a[left++];
while(right < n)
tmpArray[i++] = a[right++];
for(i = 0; i < n; i++)
a[i] = tmpArray[i];
return 0;
}
int mergeSort(int a[], int n)
{
int mid;
if(n > 1)
{
mid = n/2;
mergeSort(a,mid);
mergeSort(a+mid,n-mid);
mergeArray(a,mid,n);
}
return 0;
}```

misc.c:

```#include <stdio.h>
#include <time.h>
#include <stdlib.h>

void fillArray(int a[], int n)
{
int i;
srand(time(NULL));
for(i = 0; i < n; i++)
a[i] = rand();
}
void printArray(int a[], int n)
{
int i;
printf("%d",a[0]);
for(i = 1; i < n; i++)
printf(" %d",a[i]);
printf("\n");
}
void testSort(int a[], int n, int (*sort)(int a[], int n))
{
printf("the initial array is:\n");
printArray(a,n);
sort(a,n);
printf("\nAfter sorting,the array is:\n");
printArray(a,n);
}
void swap(int *x, int *y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
```

misc.h:

```#ifndef MISC_H
#define MISC_H

#define ARRLEN(a) (sizeof(a)/sizeof(a[0]))
void fillArray(int a[], int n);
void printArray(int a[], int n);
void testSort(int a[], int n, int (*sort)(int a[], int n));
void swap(int *x, int *y);
#endif
```

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊