【C语言】冒泡排序，选择排序，插入排序，堆排序_c语言二叉树堆排序

冒泡排序【稳定排序】

///冒泡
void BubbleSort(int arr[], int len){
	if (len <= 1){
		return;
	}
	int bound = 0;
	for (; bound < len; bound++){
		int cur = len - 1;
		for (; cur>bound; cur--){
			if (arr[cur] < arr[bound]){
				swap(&arr[cur], &arr[bound]);
			}
		}
	}
}

选择排序

“打擂台”

///选择排序//
void SelectSort(int arr[], int len){
	if (len <= 1){
		return;
	}
	int bound = 0;
	for (; bound < len; bound++){
		int cur = bound + 1;
		for (; cur < len; cur++){
			if (arr[bound]>arr[cur]){
				swap(&arr[bound], &arr[cur]);
			}
		}
	}
}

插入排序【稳定排序】

1. 定义好边界。
2. 保存bound指向的元素
3. 从后往前的去找一个合适的防治bound_value的位置，一边找一边搬运。

特点：

• 当数组元素个数比较小的时候，执行效率比较快
• 如果数组基本有序，执行效率会很高

插入排序///
void InserSort(int arr[], int len){
	if (len <= 1){
		return;
	}
	int bound = 1;
	for (; bound < len; bound++){
		int bound_value = arr[bound];
		int cur = bound;
		for (; cur>0; cur--){
			if (arr[cur - 1] > bound_value){
				arr[cur] = arr[cur - 1];
			}
			else
			{
				break;
			}
		}
		arr[cur] = bound_value;
	}
}

堆排序

堆的性质：完全二叉树

        如果是小队，父节点的值小于子节点，如果是大堆，反之。

堆排序步骤：

1. 基于数组建堆
2. 循环删除堆顶元素，将所有的元素都删除，排序完成

int cmp(int a, int b){
	return a > b ? 1 : 0;
}
 
void AdjustDown(int arr[], int len, int index){
	size_t parent = index;
	size_t child = 2 * parent + 1;
	while (child<len){
		if (child + 1<len&&cmp(arr[child + 1], arr[child])){
			child = child + 1;
		}
		if (cmp(arr[child], arr[parent])){
			swap(&arr[child], &arr[parent]);
		}
		else{
			break;
		}
		parent = child;
		child = parent * 2 + 1;
	}
	return;
}
void AdjustUp(int arr[], int len, int index){
	if (len <= index){
		return;
	}
	size_t child = index;
	size_t parent = (child - 1) / 2;
	while (child>0){
		if (cmp(arr[child], arr[parent])){
			swap(&arr[child], &arr[parent]);
		}
		else{
			break;
		}
		child = parent;
		parent = (child - 1) / 2;
	} 
}
void HeapPop(int arr[], int len){
	swap(&arr[0], &arr[len - 1]);
	AdjustDown(arr, len-1, 0);
}
void HeapCreate(int arr, int len){
	if (len <= 1){
		return;
	}
	int i =len-1;
	for (; i > 0; --i){
		AdjustUp(arr, len, i);
	}
	AdjustUp(arr, len, 0);
}
 
void heapSort(int arr[], int len){
	HeapCreate(arr, len);
	int i = 0;
	for (; i < len-1; i++){
		HeapPop(arr, len - i);
	}
	int left = 0;
	int right = len - 1;	
}

希尔排序【稳定排序】------分组式的插入排序

gap:步长，指同组元素之间的下表间隔

gap取值：N/2,N/4,N/8......1；

void shellSort(int arr[], int len){
	int gap = 0;
	for (gap = len / 2; gap >= 1; gap = gap / 2){
		int i = 0;
		for (; i < len / gap; i++){
			int j = i + gap;
			for (; j < len; j = j + gap){
				if (arr[i]>arr[j]){
					swap(&arr[i], &arr[j]);
				}
				else{
					break;
				}
			}
		}
	}
}