基本排序(C语言版)

原创
2017/01/03 19:40
阅读数 35

###冒泡排序

/**
 * 冒泡排序 logN^2
 * 基本思路:每次从数组底端将最小的数“冒”上来
 * 
 **/
void BubbleSort(int *p, int len){
	for(int i=0; i<len-1; i++){
		for(int j=len-1; j>i; j--){
			if(*(p+j)<*(p+j-1)){
				*(p+j) ^= *(p+j-1);
				*(p+j-1) ^= *(p+j);
				*(p+j) ^= *(p+j-1);
			}
		}
	}
}

###选择排序

/**
 * 选择排序 logN^2
 **/
void SelectSort(int *p, int len){
	for(int i=0; i<len-1; i++){
		int min = i;
		for(int j=len-1; j>i; j--){
			if(*(p+j)<*(p+min)) min = j;
		}
		if(min != i){
			*(p+i) ^= *(p+min);
			*(p+min) ^= *(p+i);
			*(p+i) ^= *(p+min);
		}
	}
}

###插入排序

/**
 * 插入排序 logN^2
 **/
void InsertSort(int *p, int len){
	for(int i=0; i<len-1; i++){
		for(int j=i+1; j>0; j--){
			if(*(p+j)<*(p+j-1)){
				*(p+j) ^= *(p+j-1);
				*(p+j-1) ^= *(p+j);
				*(p+j) ^= *(p+j-1);
			}else break;
		}
	}
}

###希尔排序

 /**
  * 希尔排序 N^1.5
  * 基本思路:选取某个增量,将数组分为若干的子序列,对子序列进行插入排序,
  * 逐渐减小增量,重复上述操作,直到增量为1,此时数组基本有序,最后进行一次插入排序。
  **/
void ShellSort(int *p, int len){
	for(int incre=len/2; incre>=1; incre--){
		for(int i=0; i<incre; i++){
			for(int j=i+incre; j<len; j+=incre){
				for(int k=j; k>i; k-=incre){
					if(*(p+k)<*(p+k-incre)){
						*(p+k) ^= *(p+k-incre);
						*(p+k-incre) ^= *(p+k);
						*(p+k) ^= *(p+k-incre);
					}else break;
				}
			}
		}
	}
}

###快速排序

/**
 * 快速排序 N*logN
 **/
 void QuickSort(int *p, int len){
	 if(len<=1) return;
	 int *b = p;
	 int *e = p + len - 1;
	 int sentry = *p;
	 while(b<e){
		 while(b<e && *e >= sentry) e--;
		 *b = *e;
		 while(b<e && *b <= sentry) b++;
		 *e = *b;
	 }
	 *b = sentry;
	 QuickSort(p, b-p);
	 QuickSort(b+1, len-(b-p)-1);
 }

###归并排序

/**
 * 归并排序 N*logN
 * 需要额外的空间存放数据
 * 基本思想:将一个数组分成两份,如果这两份数组的有序的,那么将这两份数组归并,
 * 对上述操作进行递归操作,直到分成的数组仅仅只有一个元素,那么它理所当然是有序的。
 **/
void MergeArray(int *p, int len1, int *q, int len2){
	int temp[len1+len2];
	int i,j,k;
	i = j = k = 0;
	while(i<len1 && j<len2){
		if(*(p+i)<*(q+j)){
			temp[k++] = *(p+i++);
		}else{
			temp[k++] = *(q+j++);
		}
	}
	while(i<len1) temp[k++] = *(p+i++);
	while(j<len2) temp[k++] = *(q+j++);
	for(i=0; i<len1+len2; i++) *(p+i) = temp[i];
}
 
void MergeSort(int *p, int len){
	if(len<=1) return;
	int middle = len/2;
	MergeSort(p, middle);
	MergeSort(p+middle, len-middle);
	MergeArray(p, middle, p+middle, len-middle);
}

###堆排序

/**
 * 堆排序 N * logN
 * len/2 -1 最后一个节点的父节点
 * 2*i + 1 左孩子节点
 * 2*i + 2 右孩子节点
 * 基本思路:将一个数组看作是完全二叉树,先调整整个堆,然后将根节点和
 * 末节点互换,重新调整堆
 **/
void HeapAdjust(int *p, int len, int i){
	int child = 2*i+1;
	if(child>=len) return;
	if(child<len-1 && *(p+child)<*(p+child+1)) child++;
	if(*(p+i)<*(p+child)){
		*(p+i) ^= *(p+child);
		*(p+child) ^= *(p+i);
		*(p+i) ^= *(p+child);
		HeapAdjust(p, len, child);
	}	
}

void HeapSort(int *p, int len){
	
	//首先先从最后一个节点的父节点开始调整堆
	for(int i=len/2-1; i>=0; i--) HeapAdjust(p, len, i);
	
	for(int i=len-1; i>0; i--){
		*p ^= *(p+i);
		*(p+i) ^= *p;
		*p ^= *(p+i);
		HeapAdjust(p, i, 0); // <--not i+1
	}	
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部