[数据结构与算法]7种排序算法

7种排序算法

#pragma once
#include<iostream>
#include<string>
/*#define SWAP1(x,y){x=x^y;y=x^y;x=x^y;}//不能用于同址交换，如SWAP(arr[1],arr[1]);会获得0值！
#define SWAP2(x,y){int temp;temp=x;x=y;y=temp;}//最保险的交换方式
#define SWAP3(x,y){x=x+y;y=x-y;x=x-y;}//可能溢出,x值高出边界*/
using namespace std;
class sort {
public:
	void SWAP1(int &x, int &y) { x = x ^ y; y = x ^ y; x = x ^ y; }//不能用于同址交换，如SWAP(arr[1],arr[1]);会获得0值！
	void SWAP2(int &x, int &y) { int temp; temp = x; x = y; y = temp; }//最保险的交换方式
	void SWAP3(int &x, int &y) { x = x + y; y = x - y; x = x - y; }//可能溢出,x值高出边界

	void SWAP(int &x, int &y) {//int &x,int &y
		if (x != y) {
			SWAP1(x, y);
		}
		else {
			SWAP2(x, y);
		}
	}

	void selectsort(int arr[], int len) {//选择排序
		int i, j;
		int index;
		for (i = 0; i < len; i++) {
			index = i;
			for (j = i + 1; j < len; j++) {
				index = (arr[j] < arr[index]) ? j : index;
			}
			//2,1,4,3,5当i=1,index=1,SWAP(arr[1],arr[1]);同值亦或得0值,导致交换失败
			SWAP(arr[i], arr[index]);
		}
	}

	void bobsort(int arr[], int len) {//冒泡排序
		int i, j;
		for (i = 0; i < len; i++) {
			for (j = 0; j < len - i - 1; j++) {
				if (arr[j] > arr[j + 1]) { SWAP(arr[j], arr[j + 1]); }
			}
		}
	}

	void insertsort1(int arr[], int len) {//直接插入排序
		int i, j;
		for (i = 1; i < len; i++) {
			for (j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
				SWAP(arr[j], arr[j + 1]);
			}
		}
	}

	void insertsort2(int arr[], int len) {//间接插入排序
		int i, j;
		int tmp;
		for (i = 1; i < len; i++) {
			tmp = arr[i];
			for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {
				arr[j + 1] = arr[j];
			}
			SWAP(arr[j + 1], tmp);
		}
	}

	void hillsort(int arr[], int len) {//希尔排序
		int i, j;
		int tmp, d;
		d = len >> 1;
		while (d > 0) {
			for (i = d; i < len; i++) {
				tmp = arr[i];
				for (j = i - d; j >= 0 && arr[j] > tmp; j -= d) {
					arr[j + d] = arr[j];
				}
				SWAP(arr[j + d], tmp);
			}
			d >>= 1;
		}
	}

	void quicksort(int arr[], int low, int high) {//快速排序
		int t = arr[low];
		int f = low + 1;
		int b = high;
		if (low >= high) return;
		while (f <= b) {
			while (f <= b && arr[f] <= t) f++;
			while (f <= b && arr[b] >= t) b--;
			if (f < b) {
				SWAP(arr[f], arr[b]);
				f++;
				b++;
			}
		}
		arr[low] = arr[b];
		arr[b] = t;
		quicksort(arr, low, b - 1);
		quicksort(arr, b + 1, high);
	}
	//堆排两步法
	void heapify1(int arr[], int len) {//变为大更堆
		int i = 0;
		while (i < len) {
			if ((2 * i + 1) < len && (2 * i + 2) < len) {
				int *lc = &arr[2 * i + 1];
				int *rc = &arr[2 * i + 2];
				int *p = (*lc > *rc) ? lc : rc;
				if (*p > arr[i]) {
					SWAP(*p, arr[i]);
					i = 0;
				}
				else {
					i++;
				}
			}
			else if ((2 * i + 1) < len) {//只有左孩子
				int lc = arr[2 * i + 1];
				if (lc > arr[i]) {
					SWAP(arr[2 * i + 1], arr[i]);
					i = 0;
				}
				else {
					i++;
				}
			}
			else {
				i++;
			}
		}
	}

	void heapsort1(int arr[], int len) {//堆排序1
		while (len > 0) {
			heapify1(arr, len);
			SWAP(arr[0], arr[len - 1]);
			len--;
		}
	}
	
	//堆排三步法：
	void heapify2(int arr[], int index,int heapsize) {
		int lc = index * 2 + 1;//lc表示左孩子
		while (lc < heapsize) {
			int largest = (lc + 1 < heapsize && arr[lc + 1] > arr[lc]) ? lc + 1 : lc;//lc+1表示右孩子;将左右孩子中最大的给largest
			largest = arr[largest] > arr[index] ? largest : index;//父和最大孩子谁大把其下标给largest；
			if (largest == index) {
				break;
			}
			SWAP2(arr[largest], arr[index]);
			index = largest;
			lc = index * 2 + 1;
		}
	}//(优于heap1)

	void heapinsert(int arr[], int index) {//使得index节点与其孩子满足大更堆规范（3个节点间）
		while (arr[index] > arr[(index - 1) / 2]) {
			SWAP2(arr[index], arr[(index - 1) / 2]);
			index = (index - 1) / 2;
		}
	}

	void heapsort2(int arr[], int len) {//堆排序2
		if (arr == NULL || len < 2) {//判断数组规范
			return;
		}
		for (int i = 0; i < len; i++) {//使得index节点与其孩子满足大更堆规范（3个节点间）
			heapinsert(arr, i);
		}
		int heapsize = len;
		SWAP2(arr[0], arr[--heapsize]);//交换大更堆的头尾
		while (heapsize > 0) {
			heapify2(arr, 0, heapsize);//恢复大更堆
			SWAP2(arr[0], arr[--heapsize]);//交换大更堆的头尾
		}
	}

	/*归并排序：
		核心merge算法：从中间将arr分为两半：L—M 和 M+1—R，
		从L开始和M+1开始分别到M和R结束的元素比较，较小的传入临时数组T中，
		最后剩下没有比较的元素直接传入T中，
		最后将T中的元素覆盖arr原来的元素；

		process算法:通过分治递归回溯给左右两半merge提供由小到大的不同mid，以此由小到大的范围执行merge；
		process(arr,L, mid);//先是左半部分递归回溯
		process(arr, mid + 1, R);//再是右半部分递归回溯
		merge(arr, L, mid, R);//第一次回溯中，左右部分各一个，merge得到最小段的有序序列，往后继续回溯。。。

		mergesort算法:确定数组合法且长度合理，随后执行process；
	*/
	void mergesort(int arr[],int len) {
		if (arr == NULL || len < 2) {
			return;
		}
		process(arr,0,len-1);
	}

	void process(int arr[], int L, int R) {
		if (L == R) {
			return;
		}
		int mid = L + ((R - L) >> 2);
		process(arr,L, mid);
		process(arr, mid + 1, R);
		merge(arr, L, mid, R);
	}

	void merge(int arr[], int L, int M, int R) {
		int len = R - L + 1;
		int *T = new int[len];
		int p1 = L;
		int p2 = M + 1;
		int i=0;
		while (p1 <= M && p2 <= R) {
			T[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
		}
		while (p1<=M) {
			T[i++] = arr[p1++];
		}
		while (p2 <= R) {
			T[i++] = arr[p2++];
		}
		for (i = 0; i < len;i++) {
			arr[L+i] = T[i];
		}
	}

	void printArr(int arr[], int len) {//输出数组
		int i;
		for (i = 0; i < len; i++) {
			cout << arr[i] << "\t";
		}
	}
};

测试：

#include<iostream>
#include<fstream>
#include<string>
#include<ctime>//clock()函数
#include"sort.h"
#define MAXSIZE 100
using namespace std;

void Print_runtime() {
	cout << clock() <<"us"<< endl;
}
int main() {
	string str;
	sort S;
	int arr[MAXSIZE];
	int length=5;
	fstream testfile;
	//从test文本中读取数据，初始化数组：
	testfile.open("test.txt", ios::in);
	if (!testfile.is_open()) { cout << "false!" << endl; }
	int i;
	for (i = 0; i < length; i++) {
		testfile >> arr[i];
	}
	S.printArr(arr, length);
	//选择排序方式：
	printf("\nInput sort name:(bob,insert1,insert2,hill,select,quick,heap1,heap2,merge):\n");
	cin >> str;
	if (str.find("bob") != string::npos) {S.bobsort(arr,length); Print_runtime();}//冒泡排序
	else if (str.find("insert1") != string::npos) { S.insertsort1(arr, length); Print_runtime(); }//插入排序1
	else if (str.find("insert2") != string::npos) { S.insertsort2(arr, length); Print_runtime();}//插入排序2
	else if (str.find("hill") != string::npos) { S.hillsort(arr,length); Print_runtime();}//希尔排序
	else if (str.find("select") != string::npos) { S.selectsort(arr, length); Print_runtime();}//选择排序
	else if (str.find("quick") != string::npos) { S.quicksort(arr,0,length-1); Print_runtime();}//快速排序
	else if (str.find("heap1") != string::npos) { S.heapsort1(arr,length - 1); Print_runtime();}//堆排序
	else if (str.find("heap2") != string::npos) { S.heapsort2(arr, length); Print_runtime();}//堆排序
	else if (str.find("merge") != string::npos) { S.mergesort(arr,length); Print_runtime();}//归并排序
	S.printArr(arr, length);
	system("pause");
}
/*要点记录：
1.要使用相对路径时，应将文件放在cpp文件所处的文件夹中。
*/