排序算法類（待完善）

 不多說廢話了，直接貼上代碼，個人把常用的排序算法寫成了一個類，友善随時調用，部分内容待後續補充

//main.cpp

#include "sort.h"
int main() {

	Sort sort_class;
	int test_array[10] = { 10,5,5,9,3,55,6,3,1,0 };
	sort_class.len = sizeof(test_array) / sizeof(test_array[0]);
	// sort_class.bubbleSort(test_array);
	//sort_class.half_insertSort(test_array);
	sort_class.shellSort(test_array);
	sort_class.print(test_array);

	return 0;
}
           

#pragma once
//sort.h

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <math.h>
using namespace std;
#define ElemType int
class Sort {
public:
	int len;
	// 交換排序
	void bubbleSort(ElemType *array);

	int partition(ElemType *array, int low, int high); //劃分函數是快排的關鍵
	void quickSort(ElemType *array, int low, int high); // 實際執行的是這個
	void quickSort(ElemType *array);	//調用這個即可，為了統一各個排序函數的調用方式

	// 選擇排序
	void selectSort(ElemType *array);
	void heapSort(ElemType *array);

	// 插入排序
	void insertSort(ElemType *array);
	void half_insertSort(ElemType *array); //折半插排
	void shellSort(ElemType *array);

	void swap(ElemType *array, int i, int j);
	void print(ElemType *array);
};
           

//sort.cpp

#include "sort.h"

void Sort::swap(ElemType *array, int i, int j) {
	auto temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

void Sort::bubbleSort(ElemType *array) {

	printf("bubbleSort:\n");
	for (int i = 0; i < len; i++) {
		bool flag = false;
		for (int j = i + 1; j < len; j++) {
			if (array[i] > array[j]) {
				swap(array, i, j);
				flag = true;  // 如果本輪周遊發生交換，則則設定flag
			}
		}
		if (flag == false) {
			return; //說明剩下的都是有序了，相比無flag比較次數少點
		}
	}
}

int Sort::partition(ElemType *array, int low, int high) {
	auto pivot = array[low]; // 将目前表中第一個元素作為樞軸元素，占用O（1）的空間 這時候low已經備份，可以覆寫
	while (low < high) {
		while (low < high && array[high] >= pivot)
			--high; //比樞軸大的元素放在右邊不動
		array[low] = array[high]; // 碰到比樞軸小的，移到左邊  這時候high已經備份，可以覆寫
		while (low < high && array[low] >= pivot)
			++low; //比樞軸小的元素放在左邊不動
		array[high] = array[low]; // 碰到比樞軸大的，移到右邊  這時候新的low已經備份，可以覆寫
	}
	array[low] = pivot;		// 樞軸元素存放到最終的位置 将第一個備份的放回去
	return low;		//傳回樞軸元素的位置
}
void Sort::quickSort(ElemType *array, int low, int high) {
	int pivotPos = 0;
	while (low < high) {
		pivotPos = partition(array, low, high);
		quickSort(array, low, pivotPos); // 對左邊部分遞歸快排
		quickSort(array, pivotPos, high); //對又變部分遞歸快排
	}
}
void Sort::quickSort(ElemType *array) {
	/*
	快排是對冒泡排序的一種改進。
	基本思想：基于分治法
	*/
	printf("quickSort:\n");
	int low = 0, high = len - 1;
	quickSort(array, low, high);
}

void Sort::selectSort(ElemType *array) {
	/* 簡單選擇排序
	基本思想：每一趟（如第i趟）在後面n-i+1（i=1,2...,n-1）個待排序元素中選取關鍵字最小的元素，作為有序子序列的第i個元素。
	選擇排序的時間複雜度為：O(n^2)，空間複雜度：O(1)
	選擇排序是不穩定的；
	*/
	printf("selectSort:\n");
	int min_pos; //記錄最小元素的位置
	for (int now_start = 0; now_start < len - 1; now_start++) {
		min_pos = now_start; 
		for (int j = now_start+1; j < len; j++) {
			if (array[j] < array[min_pos]) 
				min_pos = j;	//更新最小元素的位置 
		}
		if (min_pos != now_start)
			swap(array, now_start, min_pos);	// 将第i小的元素與第i個位置的元素互換
	}
}

void Sort::heapSort(ElemType *array) {
	/*
	堆排序是一種樹形選擇排序方法
	*/
	printf("heapSort:\n");
}

void Sort::insertSort(ElemType *array) {
	/*
	直接插入排序
	基本思想：每次将一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子序列中
	感覺像是逐漸周遊逆序數
	适用于基本有序的排序表和資料量不大的排序表
	*/
	printf("insertSort:\n");
	int i, j;
	int temp;
	for (i = 1; i < len; i++) {
		if (array[i] < array[i - 1]) {
			temp = array[i];	//哨兵，好多情況下把array[0]作為哨兵，不存放元素，數組總長度為n+1，我這裡單獨搞了一個temp，考慮到這是一個類，盡量和其他的排序方法參數相容
			for (j = i - 1; temp < array[j]; j--)
				array[j + 1] = array[j]; //元素後移
			array[j + 1] = temp; // 發現第j個位置的元素已經小于temp,是以把temp放到第j+1個位置
		}
	}

}
void Sort::half_insertSort(ElemType *array) {
	/*
	折半插入排序
	基本思想：與直接插排的差別在于，直接插排是邊比較變移動，需要移動多少個就需要比較多少次
	而折半插排是将比較和移動這兩個操作進行了分離，先确定插入位置，再移動元素，
	好處在于：折半查找的方式減少了比較的次數
	注：移動操作的次數無論如何是不能被減少的（除非你用連結清單，就不需要移動了，但是用了連結清單之後折半查找方式就行不通了）
	*/
	printf("half_insertSort:\n");
	int i, j;
	int temp;
	int low, high, mid;
	for (i = 1; i < len; i++) {
		if (array[i] < array[i - 1]) {
			temp = array[i];	//哨兵，好多情況下把array[0]作為哨兵，不存放元素，數組總長度為n+1，我這裡單獨搞了一個temp，考慮到這是一個類，盡量和其他的排序方法參數相容
			low = 0; high = i - 1;
			// 
			while (low <= high) {
				mid = (low + high) / 2;
				if (array[mid] < temp)
					low = mid + 1;
				else high = mid - 1;
			}
			for (j = i - 1; j > high; j--)
				array[j + 1] = array[j]; //元素後移
			array[high + 1] = temp; // 發現第j個位置的元素已經小于temp,是以把temp放到第j+1個位置
		}
	}
}
void Sort::shellSort(ElemType *array) {
	/*
	希爾排序（有稱縮小增量排序）
	基本思想：彌補直接插排的缺陷（隻适用于基本有序的和資料量不大的），
	步長的了解：并不是按照多少步長進行劃分一組，比如dk,dk+1,...,2dk-1是一組
	而是dk,2dk,3dk...這些是一組。注意差別歸并排序
	*/
	printf("shellSort:\n");
	int dk;
	int temp;
	int i, j;
	for (dk = len / 2; dk >= 1; dk /= 2) {
		for (i = dk + 1; i < len; i++) {	//在每一個組裡面采用的仍舊是插入排序
			if (array[i] < array[i - dk]) {
				temp = array[i];
				for (j = i - dk; j >= 0 && temp < array[j]; j -= dk)
					array[j + dk] = array[j];
				array[j + dk] = temp;
			}
		}
	}
}

void Sort::print(ElemType *array) {
	for (int i = 0; i < len; i++)
		printf("%d ", array[i]);
}