七大排序的C语言实现

Talk is cheap, show me your code!

不要介意夹了一点C++

c

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

inline void swap(int &a, int &b) {
	int tmp = a;
	a = b;
	b = tmp;
}

void bubbleSort(int ary[], int len) {
	for(int i = 0; i < len; i++)
		for(int j = 0; j < len-i; j++)
			if(ary[j] > ary[j+1])
				swap(ary[j], ary[j+1]);
	return;
}

void selectSort(int ary[], int len) {
	for(int i = 0; i < len; i++) {
		int minIndex = i;
		for(int j = i; j < len; j++)
			if(ary[j] < ary[minIndex])
				minIndex = j;
		swap(ary[i], ary[minIndex]);
	}
	return;
}

inline void _insertSort(int ary[], int len, int gap, int startIndex) {
	for(int i = startIndex + 1; i < len; i += gap)
		for(int j = i-gap; j >= startIndex && ary[j] > ary[j+gap]; j -= gap)
			swap(ary[j], ary[j+gap]);
	return;
}

void insertSort(int ary[], int len) {
	_insertSort(ary, len, 1, 0); // 起始位置为0，间隔为1的插入排序 
}

void quickSort(int ary[], int len) {
	if(len < 2)
	// 当列表长度为1时，有序，不做任何操作 
		return;
	if(len == 2) {
	// 当列表长度为2时，比较两个元素的大小，然后调整并返回 
		if(ary[0] > ary[1])
			swap(ary[0], ary[1]);
		return;
	}
	int left = 0;
	int right = len - 1;
	while(left < right) {
		// 基准值为首个元素 
		while(ary[right] >= ary[0] && left < right)
			// 右哨兵左移，直到小于基准值 
			right--;
		while(ary[left] <= ary[0] && left < right)
			left++;
			// 左哨兵右移，直到大于基准值 
		swap(ary[left], ary[right]); // 交换两个不符合条件的数 
	}
	swap(ary[0], ary[right]);
	// 当左哨兵和右哨兵相遇后，这个地方的数不比基准值大，所以将它与基准值交换
	// 这时基准值左边的数都比基准值小，右边的都比基准值大 
	quickSort(ary, right);
	// 对基准值左边的数组进行排序 
	quickSort(ary+right+1, len-right-1);
	// 对基准值右边的数组进行排序 
	return;
}

inline void siftDown(int ary[], int len, int startIndex) {
	int i = startIndex;
	for(int j = i*2+1; j < len; j = j*2+1) {
	// i为当前节点index, j为左子节点index
		if(j+1 < len && ary[j] < ary[j+1])
		// 找出左右子节点中比较大的那个 
			j++;
		if(ary[i] < ary[j])
		// 如果子节点大于父节点 
			swap(ary[i], ary[j]);
			// 交换父子节点 
		else
			return;
		i = j; //父节点下移 
	}
	return;
}

void heapSort(int ary[], int len) {
	for(int i = (len-1) / 2; i >= 0; i--)
	//建堆，复杂度O(n/2) 
		siftDown(ary, len, i);
	while(len > 1) {
		swap(ary[0], ary[--len]);
		// 交换堆顶元素与最后一个元素，并将无序表长度自减 
		siftDown(ary, len, 0); 
	}
	return;
}

void mergeSort(int ary[], int len) {
	if(len < 2)
	// 当列表长度为1时，有序，不做任何操作 
		return;
	int mid = len / 2;
	// 将数组从中间切开，分为左数组和右数组 
	int leftLen = mid;
	int rightLen = len - mid;
	mergeSort(ary, leftLen);
	// 将左数组排序 
	mergeSort(ary+mid, rightLen);
	// 将右数组排序 
	int i, j;
	int leftAry[leftLen], rightAry[rightLen];
	for(i = 0; i < leftLen; i++)
		leftAry[i] = ary[i];
	for(j = mid; j < len; j++)
		rightAry[j-mid] = ary[j];
	// 分配另外两块内存，用于存储左数组和右数组的拷贝 
	i = j = 0;
	while(i < leftLen && j < rightLen)
		ary[i+j] = (leftAry[i] < rightAry[j])? 
					leftAry[i++]: 
					rightAry[j++];
	while(i < leftLen)
		ary[i+j] = leftAry[i++];
	while(j < rightLen)
		ary[i+j] = rightAry[j++];
	// 合并两个有序数组，最差复杂度为O(n) 
	return;
}

void shellSort(int ary[], int len) {
	int gap = len;
	while(gap /= 2)
		for(int i = 0; i < gap; i++)
			_insertSort(ary, len, gap, i);
	return;
}

bool isOrdered(int ary[], int len) {
	return (len < 2)? true : ((ary[0] <= ary[1]) && isOrdered(ary+1, len-1));
}

void bogoSort(int ary[], int len) {
	// 彩蛋——马骝排序，复杂度O(n!) 
	srand(time(NULL));
	while(!isOrdered(ary, len))
		// 打乱数组 
		for(int i = 0; i < len; i++) {
			int a = rand() % len;
			int b = rand() % len;
			swap(ary[a], ary[b]);
		}
	return;
}

int main() {
	const int N = 1 << 10;
	const int MAX_RANGE = 10000; 
	int ary[N];
	srand(time(NULL));
	printf("排序前：\n");
	for(int i = 0; i < N; i++) {
		ary[i] = rand() % MAX_RANGE;
		printf("ary[%d]=%d\n", i, ary[i]);
	}
	printf("------------\n排序后：\n");
	quickSort(ary, N);
	for(int i = 0; i < N; i++)
		printf("ary[%d]=%d\n",i,ary[i]);
	printf("%s",isOrdered(ary,N) ? "有序" : "无序");
}