数据结构与算法--几种排序的实现(C++)

数据结构与算法--几种排序的实现(C++)

简单的几个排序算法的实现，包括插入排序，希尔排序，选择排序，快速排序，测试函数略简略，自己重新写一个吧。

#include<iostream>
using namespace std;

//插入排序 
void insert_sort(int unsort[], int num)
{
	for (int i = 1; i < num; i++) {
		int temp = unsort[i];
		for (int j = i; j > 0; j--) {
			if (unsort[j] < unsort[j-1]) {
				unsort[j] = unsort[j-1];
				unsort[j-1]= temp;
			} else {
				break;
			}
		}
	} 

}


//选择排序 
void select_sort(int arr[], int num) {
	int current;
	for (int i = num - 1; i >= 0;  i--) {
		current = i;
		for (int pre = 0; pre <= i-1; pre++) {
			if (arr[pre] > arr[current])
				current = pre;		
		}
		int temp = arr[i];
		arr[i] = arr[current];
		arr[current] = temp;
	}
}


//希尔排序 
void shell_sort(int arr[], int num) {
	int inc, start;
	inc = num;
	while (inc > 1) {
		inc = inc / 3 + 1;
		for (start = 0; start < inc; start++) {
			for (int i = start + inc; i < num; i += inc) {
				int pre = arr[i];
				int index = i;
				while (pre < arr[index - inc] && index - inc >= 0) {
					arr[index] = arr[index - inc];
					index -= inc;
				}
				arr[index] = pre;
			}
		}
	}
}

//快速排序 
void quick_sort(int low, int high, int arr[]){
	if (low >= high) return;
	int pivot = arr[low];
	int l = low, h = high;
	while (l < h) {
		while (l < h&&arr[h] >= pivot)
			h--;
		if (l < h)
			arr[l++] = arr[h];
		while (l < h&&arr[l] < pivot)
			l++;
		if (l < h)
			arr[h--] = arr[l];
	}
	arr[l] = pivot;
	quick_sort(low, l - 1, arr);
	quick_sort(l + 1, high, arr);
}

//测试函数 
int main()
{
	int a[15];
	for (int i = 0; i < 15; i++) {
		cin >> a[i];
	}
	insert_sort(a, 15);
	for (int i = 0; i < 15; i++) {
		cout << a[i] << " ";
	}
}