排序算法总结

标签（空格分隔）： 排序算法

---

1、选择排序

typedef int DATATYPE

void swap(DATATYPE* a, DATATYPE* b) {
	DATATYPE temp;
	temp = *b;
	*b = *a;
	*a = temp;
}

//选择排序
void selectSorted(DATATYPE a[], int length)
{
	assert(a != NULL);
	int max;
	for (int i = 0; i < length - 1; i++) {
		max = 0;
		for (int j = 1; j < length - 1 - i; j++) {
			if (a[max] < a[j]) {
				max = j;
			}
		}
		if (max != length - 1 - i) {
			swap(&a[max], &a[length - 1 - i]);
		}
	}

}

2、冒泡排序

typedef int DATATYPE

void swap(DATATYPE* a, DATATYPE* b) {
	DATATYPE temp;
	temp = *b;
	*b = *a;
	*a = temp;
}
//冒泡排序
void bubbleSorted(DATATYPE a[], int len) {
	assert(a != NULL);
	bool sorted = true;
	for (int i = 0; i < len - 1; i++) {
		sorted = true;
		for (int j = 0; j < len - 1 - i; j++) {
			if (a[j] > a[j + 1]) {
				swap(&a[j], &a[j + 1]);
				sorted = false;
			}
		}
		if (sorted) {
			break;
		}
	}

}

3、插入排序

typedef int DATATYPE

//插入排序
void insertSorted(DATATYPE a[], int len)
{
	assert(a != NULL);
	int preIndex, curData;
	for (int i = 1; i < len; i++)
	{
		preIndex = i - 1;
		curData = a[i];
		while (preIndex >= 0 && a[preIndex] > curData) {
			a[preIndex + 1] = a[preIndex];
			preIndex--;
		}
		a[preIndex + 1] = curData;
	}
	
}

4、希尔排序

typedef int DATATYPE

//希尔排序	缩小增量的插入排序
void shellSorted(DATATYPE a[], int len)
{
	int gap = len / 2;
	while (gap > 0) {
		for (int i = gap; i < len; i++) {
			int curData = a[i];
			int preIndex;
			for (preIndex = i - gap; preIndex >= 0 && a[preIndex] > curData;) {
				a[preIndex + gap] = a[preIndex];
				preIndex = preIndex - gap;
			}
			a[preIndex + gap] = curData;
		}
		gap /= 2;
	}
}

5、快速排序

typedef int DATATYPE
//插入排序 去基准数，将大于等于它的数放在右边，小于他的数放左边，返回插入位置的下标
int partiton(DATATYPE a[], int low, int high) {
	assert(a != NULL );
	int i = low;
	int j = high;
	int base = a[low];
	if (low < high) {
		while (i < j) {
			while (i < j && a[j] >= base) j--;
			if (i < j)
			{
				a[i++] = a[j];
			}
			while (i < j && a[i] < base) i++;
			if (i < j) {
				a[j--] = a[i];
			}
		}
		a[i] = base;
	}
	return i;
}

//分治思想 递归排序
void quickSorted(DATATYPE a[], int low, int high)
{
	assert(a != NULL);
	if (low < high) {
		int index = partiton(a, low, high);
		quickSorted(a, low, index - 1);
		quickSorted(a, index + 1, high);
	}
}

6、堆排序

参考：这是去往 堆排序算法 的链接。