# 数据结构-排序

## Sort

Posted by xuepro on November 10, 2017

## 排序算法

### 插入排序、折半插入排序

#include <stdio.h>

typedef int T;

/*插入排序*/
void InsertSort(T r[],int n) {
for(int i = 1; i <n; i ++)
if(r[i]<r[i-1]) {
T temp = r[i];        /*r[i]保存起来*/
r[i] = r[i-1];    /*r[i-1]后移一个单元*/

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

int j;
for(j=i-2; j>=0&&temp<r[j]; j--)
r[j+1] = r[j];       /*每个元素后移*/

r[j+1] = temp;    /*最后把r[0]写入*/
}
}

/*折半插入排序*/
void BiInsertSort(T R[],int n) {
/* 对序列R[0],...R[n-1]作折半插入排序 */
T temp; int low,high,m;
for(int i=1; i<n; ++i ) {
temp = R[i];   /* 将R[i]暂存到R[0]*/
low = 0; high = i-1;
while(low<=high) {
/*在R[low..high]中折半查找插入的位置*/
m = (low+high)/2; /* 折半 */
if (temp < R[m])
high = m-1; /* 插入点在低半区*/
else low = m+1;  /* 插入点在高半区*/
}
for(int j=i-1; j>=high+1; --j )
R[j+1] = R[j]; /* 记录后移 */
R[high+1] = temp; /* 插入 */
}
}

void Print(T a[],int n){
for(int i = 0 ; i<n;i++)
printf("%d ",a[i]);
printf("\n");
}

int main(){
T arr[] = {49,38,65,97,76,13,27};
BiInsertSort(arr,7);
Print(arr,7);

T b[] = {49,38,65,97,76,13,27};
InsertSort(b,7);
Print(arr,7);
}



### 希尔排序

#include <stdio.h>
typedef int EType;

int LT(EType a, EType b){
if(a<b) return 1;
return 0;
}

/*只要对插入排序稍作修改,使得间隔为d的属于
一个子序列进行插入就可以了*/

void InsertShellPass(EType a[], int n,int d) {
int i,j; EType t;
for(i = d; i < n; i ++)
if(LT(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&&LT(t,a[j]); j-=d)
a[j+d] = a[j];       //每个元素后移

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

void ShellSort(EType a[],int n){
int ds[] = {7,5,3,1};
for(int i = 0 ; i<4;i++)
InsertShellPass(a,n,ds[i]);
}
void Print(EType a[],int n){
for(int i = 0 ; i<n;i++)
printf("%d ",a[i]);
printf("\n");
}

int main(){
EType arr[] = {49,38,65,97,76,13,27};

ShellSort(arr,7);
Print(arr,7);
}


### 冒泡排序Bubble sort


/* Bubble sort */
#include <stdio.h>

typedef int T;

void swap(T *xp, T *yp)
{
T temp = *xp;
*xp = *yp;
*yp = temp;
}

/*
void bubbleSort(T arr[], int n){
int i, j;
for (i = n-1; i>0; i--)
for (j = 0; j < i; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
*/

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

/* Function to print an array */
void printArray(T arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

/*test above functions*/
int main()
{
T arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}


### 快速排序

#include <stdio.h>

typedef int EType;

int LT(EType a, EType b){
if(a<b) return 1;
return 0;
}

void Swap(EType *a, EType *b){
EType t = *a; *a = *b; *b = t;
}

int Partition(EType data[], int low, int high){
int pivot      = low;       // 以最左元素为中轴
EType pivotvalue = data[low]; // 记录中轴的值
while(low < high) {
while(low<high && data[high] >= pivotvalue)
high --; // high向左，直到遇见比pivot小的
while(low<high && data[low] <= pivotvalue)
low ++;  // low向右，直到遇见比pivot大的
// low和high扫描受阻，交换low和high的值
Swap(&data[low], &data[high]);
}
// 交换中轴和low的值（也就是把中轴放置到正确的位置上）
Swap(&data[pivot], &data[low]);
return low;
}

void QSort(EType a[], int low, int high) {
if(low < high)  {    //待排序数列长度大于1
int pivotloc = Partition(a, low, high);
//对左子序列进行排序
QSort(a, low, pivotloc - 1);
//对右子序列进行排序
QSort(a, pivotloc + 1, high);
}
}

void Print(EType a[],int n){
for(int i = 0 ; i<n;i++)
printf("%d\t",a[i]);
printf("\n");
}
int main(){
EType arr[] = {49,38,65,97,76,13,27};
Print(arr,7);

QSort(arr,0,6);
Print(arr,7);
}


### 选择排序

#include <stdio.h>
typedef int EType;

int LT(EType a, EType b){
if(a<b) return 1;
return 0;
}

void Swap(EType *a, EType *b){
EType t = *a; *a = *b; *b = t;
}

void SelectSort(EType data[], int n) {
for(int i = 0; i < n; i ++) {
// 找到i~n-1中最小的一个IndexMin
int IndexMin = i;
for(int j = i; j < n; j ++)
if(LT(data[j], data[IndexMin]))
IndexMin = j;
// 把IndexMin和i作交换
if(IndexMin != i)
Swap(&data[IndexMin],&data[i]);
}
}

void Print(EType a[],int n){
for(int i = 0 ; i<n;i++)
printf("%d\t",a[i]);
printf("\n");
}
int main(){
EType arr[] = {49,38,65,97,76,13,27};
Print(arr,7);

SelectSort(arr,7);
Print(arr,7);
}


### 归并排序

#include <stdio.h>

#include <stdlib.h>

#include <stdio.h>

#include <malloc.h>

typedef int T;

void copy(T A[], T B[], int s, int n){
for (int i = s; i <= n; i++)
B[i] = A[i];
}
void copy(T A[], T B[], int n){
for (int i = 0; i < n; i++)
B[i] = A[i];
}
void print(T A[], int n){
for (int i = 0; i<n; i++)
printf("%d ", A[i]);
printf("\n");
}

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++];
}

/*------自顶向下的递归归并-------*/
/*[s,t]区间： A归并排序到B中 */
void TopDownMergeSort(T A[], T B[], int s, int t){
if (t == s) {
B[s] = A[s]; return;
}
TopDownMergeSort(A, B, s, (s + t) / 2);      /*[s,(s + t) / 2]区间： A归并排序到B中 */
TopDownMergeSort(A, B, (s + t) / 2 + 1, t);  /*[(s + t) / 2 + 1, t) / 2]区间： A归并排序到B中 */
merge(B, A, s, (s + t) / 2, t);       /*B中2个有序序列的一趟归并到A中*/
copy(A, B, s, t);                     /* 将数组A拷贝到B 中 */
}

/*------自底向上的迭代归并-------*/
inline T min(T a, T b){ return a < b ? a : b; }
void BottomUpMergeSort(T A[], T B[], int n){
for (int width = 1; width < n; width = 2 * width) {
/*A由宽度为width的有序序列构成（最后一个可能宽度小于width）*/
for (int i = 0; i < n; i = i + 2 * width)
{
/* 将2个有序序列A[i:i+width-1] and A[i+width:i+2*width-1] 归并到 B[] */
merge(A, B, i, min(i + width, n)-1, min(i + 2 * width, n)-1);
}
copy(B, A, n); /* 现在A由长度为2*width的有序序列构成*/
}
}

int main(){
T A[] = { 64, 34, 25, 12, 22, 11, 90 };
/* 和A同样大小的辅助数组 */
T *B = (T*)malloc(7 * sizeof(T));
print(A, 7);
/*自顶向下的递归归并*/
TopDownMergeSort(A, B, 0, 6);
/*自底向上的迭代归并*/
/*BottomUpMergeSort(A, B, 7);*/
print(B, 7);
}


### 堆排序

• C版本 c #include

/*

1. 把原始数据整理成最大堆 i = n/2 to 1 调整第i个元素[i,n]
2. 不断输出调整 2.1）输出堆顶元素 2.2）调整新堆顶元素 */

typedef int T;

void heap_adjust(T a[], int s, int m){ T t = a[s]; int j = 2*s; for(; j <= m; j *= 2) { if(j < m && a[j]< a[j+1] ) j++; //j指向s较大的“儿子” if(!(t<a[j]) ) break; //若j的值比t小，说明找到了s的位置 a[s] = a[j]; //否则元素j上移 s = j; } a[s] = t; //写入s }

void heap_sort(T a[],int n){ for(int i = n/2; i>=1; i–) heap_adjust(a,i,n);

for(int i = n; i>=2; ){ T t = a[1];a[1] = a[i]; a[i] = t; heap_adjust(a,1,–i); } }

int main() { T a[] = {-1,7,3,1,5,4,8,2}; heap_sort(a,7); for(int i = 1; i<=7;i++) printf(“%d\n”, a[i]); }


* C++(引用)版本

cpp

//---------sort.h-------

#define MAXSIZE 1024     // 最多元素个数

typedef double KeyType;   // 关键字类型

typedef char InfoType;

typedef struct{
KeyType key;       // 关键字

InfoType otherinfo;
}RedType;              // 一条数据记录

typedef struct{
RedType r[MAXSIZE+1]; // 数组

int length;           // 元素个数

}SqList;

bool LT(KeyType k1,KeyType k2) {return k1<k2;}

void swap(RedType &r1, RedType &r2){ RedType t = r1; r1 = r2; r2 = t;}

//---------------------insert sort----------------
void InsertSort(SqList &L) {
for(int i = 2; i <= L.length; i ++)
if(LT(L.r[i].key, L.r[i-1].key)) //i比i-1小

{
L.r[0] = L.r[i];      //用r[0]先记录r[i]的值

L.r[i] = L.r[i-1];    //r[i-1]后移一个单元

//从i-2开始，往左扫描，直到找到一个<=r[0]的j

int j;
for(j=i-2; LT(L.r[0].key, L.r[j].key); j--)
L.r[j+1] = L.r[j];       //每个元素后移

L.r[j+1] = L.r[0];    //最后把r[0]写入

}
}

//---------heap sort----------------

void HeapAdjust(SqList &H, int s, int m) {
RedType rc = H.r[s]; //暂时保存待下移的数据

for(int j = 2 * s; j <= m; j *= 2) {
if(j < m && LT(H.r[j].key, H.r[j+1].key))
j ++;    //j指向s较大的“儿子”

if(!LT(rc.key,H.r[j].key))
break;  //若j的值比rc小，说明找到了s的位置

H.r[s] = H.r[j]; //否则元素j上移

s = j;
}

H.r[s] = rc;   //写入s
}

void HeapSort(SqList &H){
//将H.r[1…H.length()]建成大顶堆

for(int i = H.length /2;i>0;i--)

//输出堆顶H.r[1],并调整H.r[1…i-1]

for(int i = H.length;i>1;i--){
swap(H.r[1], H.r[i]); //两者交换
}
}

//------------------main.cpp---------------

#include <stdio.h>

void OutPut(const SqList &sL){
for(int i = 1; i<=sL.length;i++){
printf("%8.2f  ",sL.r[i]);
}
printf("\n");
}

//#define TIME_TEST

#ifdef TIME_TEST

#include <time.h>

#endif

int main(){

#ifdef TIME_TEST

time_t   start, finish;
double   elapsed_time;

#endif

SqList sL;
RedType r;
r.otherinfo = 'A';
sL.length = 0;
r.key = 36;  sL.r[++sL.length] = r;
r.key = 16;  sL.r[++sL.length] = r;
r.key = 26;  sL.r[++sL.length] = r;
r.key = 66;  sL.r[++sL.length] = r;
r.key = 296; sL.r[++sL.length] = r;
r.key = 106; sL.r[++sL.length] = r;
r.key = 56;  sL.r[++sL.length] = r;

SqList tL = sL;
OutPut(tL);

#ifdef TIME_TEST

time( &start );

#endif

InsertSort(tL);

#ifdef TIME_TEST

time( &finish );
elapsed_time = difftime( finish, start );
printf( "InsertSort takes %6.0f seconds.\n", elapsed_time );
#endif

OutPut(tL);

tL = sL;
OutPut(tL);
#ifdef TIME_TEST

time( &start );

#endif

HeapSort(sL);

#ifdef TIME_TEST

time( &finish );
elapsed_time = difftime( finish, start );
printf( "HeapSort takes %6.0f seconds.\n", elapsed_time );

#endif

OutPut(tL);

return 0;
}