排序

排序算法

• 直接插入
• 折半插入
• 冒泡排序
• 简单选择排序
• 快速排序
• 堆排序

实现以及使用c++

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

void half_insert_sort(int nums[], int size) {
	// 将新数字插入到有序数组中
	// 使用折半查找寻找插入的位置
	for (int i = 0; i < size - 1; i++) {
		// [0,i]是有序数组
		// i+1是新添加的数字
		int start = 0, end = i;
		int mid;
		int temp = nums[i + 1];
		while (start < end) {
			mid = start+(end-start) / 2;
			if (nums[mid] < temp) {
				start = mid + 1;
			}
			else if (nums[mid] > temp) {
				end = mid - 1;
			}
			else {
				start = mid;
				break;
			}
		}
		for (int j = i; j > start; j--) {
			nums[j + 1]=nums[j];
		}
		if (nums[start] <= temp) {
			nums[start + 1] = temp;
		}
		else {
			nums[start + 1] = nums[start];
			nums[start] = temp;
		}
	}
}

void bubble_sort(int nums[], int size) {
	// 交换排序的一种 将最大的冒出来
	for (int i = 0; i < size; i++) {
		bool flag = false;
		for (int j = 0; j < size - i-1; j++) {
			if (nums[j] > nums[j + 1]) {
				int temp = nums[j + 1];
				nums[j + 1] = nums[j];
				nums[j] = temp;
				flag = true;
			}
		}
		if (!flag) {
			break;
		}
	}
}

int fast_sort_part(int nums[], int start, int end) {
	
	while (start < end) {
		while (start < end && nums[start] <= nums[end]) {
			start++;
		}
		if (start < end) {
			//交换
			int temp = nums[start];
			nums[start] = nums[end];
			nums[end] = temp;
		}

		while (start < end && nums[start] <= nums[end]) {
			end--;
		}
		if (start < end) {
			// 交换
			int temp = nums[start];
			nums[start] = nums[end];
			nums[end] = temp;
		}

	}
	return start;
}

void Q_sort(int nums[], int start, int end) {
	if (start < end) {
		int fenge = fast_sort_part(nums, start, end);
		// 排序 [0,fenge) (fenge,end]
		Q_sort(nums, 0, fenge-1);
		Q_sort(nums, fenge+1, end);
	}
}

// 快速排序
void fast_sort(int nums[],int size) {
	// 将小于val移到val之前 大于val的移动到val之后
	Q_sort(nums, 0, size - 1);

}

// 简单选择排序
void choose_sort(int nums[], int size) {
	for (int i = 0; i < size; i++) {
		// 做i趟 每趟选择最大的
		int i_max = size-i-1;
		for (int j = 0; j < size-i-1; j++) {
			if (nums[i_max] < nums[j]) {
				i_max = j;
			}
		}
		int temp = nums[size - i - 1];
		nums[size - i - 1] = nums[i_max];
		nums[i_max] = temp;
	}
}

void adjust_heap(int nums[], int last_index) {
	int front = nums[0];
	int i = 0;
	while (2 * i + 1 <= last_index) {// 当不是叶子的时候
		if (2 * i + 2 > last_index) {//没有右孩子
			if (front < nums[2 * i + 1]) {
				// 交换
				nums[i] = nums[2 * i + 1];
				i = 2 * i + 1;
			}
			else {
				break;
			}
		}
		else {
			if (front < nums[2 * i + 1] || front < nums[2 * i + 2]) {
				if (nums[2 * i + 1] < nums[2 * i + 2]) {
					nums[i] = nums[2 * i + 2];
					i = 2 * i + 2;
				}
				else {
					nums[i] = nums[2 * i + 1];
					i = 2 * i + 1;
				}
			}
			else {
				break;
			}
		}
	}
	nums[i] = front;

}

// 堆排序
// 什么是堆 父节点大于左右孩子节点是大根堆 小于是小根堆 建立堆 然后把最后堆顶移到最后 最后的移上去 调整堆
void heap_sort(int nums[], int size) {
	// 建堆
	// 叶子节点个数是
	int leaf_size = (size + 1) / 2;
	// 非叶子节点开始的下标为
	int index = size - leaf_size-1;
	// 初始建堆
	for (int i = index; i >= 0; i--) {
		if (2 * i + 2 >= size) {//没有右孩子
			if (nums[i] < nums[2 * i+1]) {
				// 交换
				int temp = nums[i];
				nums[i] = nums[2 * i+1];
				nums[2 * i+1] = temp;
			}
		}
		else {
			if (nums[i] < nums[2 * i+1]||nums[i]<nums[2*i+2]) {
				if (nums[2 * i+1] < nums[2 * i + 2]) {
					int temp = nums[i];
					nums[i] = nums[2 * i + 2];
					nums[2 * i + 2] = temp;
				}
				else {
					int temp = nums[i];
					nums[i] = nums[2 * i+1];
					nums[2 * i+1] = temp;
				}
			}
		}
	}
	// 
	for (int i = 0; i < size; ) {
		// 取下堆顶
		int max = nums[0];
		// 将堆尾放到堆顶
		nums[0] = nums[size - 1 - i];
		nums[size - 1 - i] = max;
		i++;
		// 调整堆[0,size-1-i]
		adjust_heap(nums, size - 1 - i);
	}
}
// 使用algorithm中的sort
bool cmp(int x,int y) {
	return x < y;// y在前 从大到小
}

// 优先队列构造堆
struct cmp_priority
{
	bool operator()(int x, int y) {
		return x < y;// y在前 大根堆
	}
};
void test(int nums[],int size) {
	priority_queue<int, vector<int>, cmp_priority> q;
	for (int i = 0; i < size; i++) {
		q.push(nums[i]);
	}
	for (int i = 0; i < size; i++) {
		cout << q.top() << " ";
		q.pop();
	}
}



int main() {
	int nums[] = { 3,4,2,2,1,6,3 };
	int size = 7;
	//half_insert_sort(nums, size);
	//bubble_sort(nums, size);
	//fast_sort(nums, size);
	//choose_sort(nums, size);
	//heap_sort(nums, size);
	//sort(nums, nums + size, cmp);


	/*for (int i = 0; i < size; i++) {
		cout << nums[i] << " ";
	}*/

	test(nums, size);
}
```cpp