十大排序算法 C++實作

十大排序算法

• 冒泡排序
• 選擇排序
• 插入排序
• 桶排序
• 計數排序
• 基數排序
• 快速排序
• 歸并排序
• 基爾排序
• 堆排序

// ConsoleApplication16.cpp : 定義控制台應用程式的入口點。
//

#include "stdafx.h"

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

//1冒泡排序
void bubbleSort(vector<int> &v)
{
	int len = v.size();
	for (int i = 0; i < len - 1; i++)
	{
		for (int j = 0; j < len - i-1; j++)
		{
			if (v[j] > v[j + 1])
			{
				int temp = v[j + 1];
				v[j+1] = v[j];
				v[j] = temp;
			}
		}
	}
}

//2選擇排序
void seletionSort(vector<int> &v)
{
	int len = v.size();
	for (int i = 0; i < len - 1; i++)
	{
		for (int j = i + 1; j < len; j++)
		{
			if (v[i] > v[j])
			{
				int temp = v[j];
				v[j] = v[i];
				v[i] = temp;
			}
		}
	}
}

//3插入排序
void insertSort(vector<int> &v)
{
	int len = v.size();
	for (int i = 1; i < len; i++)
	{
		int temp = v[i];
		int j;
		for (j = i-1; j >= 0; j--)
		{
			//目前值大于等于v[j]
			if (temp >= v[j])
			{
				break;
			}
			//目前值小于v[j]
			v[j + 1] = v[j];
		}
		v[j + 1] = temp;
	}
}

//4桶排序，n為桶的數量
void bucketSort(vector<int> &v, int n)
{
	int value_min = *min_element(v.begin(), v.end());
	int value_max = *max_element(v.begin(), v.end());
	float interval = (value_max - value_min + 1) / (float)n;
	vector<vector<int>> value_sort;
	value_sort.resize(10);

	for (int i = 0; i < v.size(); i++)
	{
		int index = (int)((v[i] - value_min) / interval);
		value_sort[index].push_back(v[i]);
	}
	for (int i = 0; i < n; i++)
	{
		bubbleSort(value_sort[i]);
	}
	int k = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < value_sort[i].size(); j++)
		{
			v[k++] = value_sort[i][j];
		}
	}
}

//5計數排序
void countSort(vector<int> &v)
{
	const int num = 100;
	int temp[num] = {0};
	for (int i = 0; i < v.size(); i++)
	{
		temp[v[i]]++;
	}
	int k = 0;
	for (int i = 0; i < num; i++)
	{
		//i表示數組中出現的數，temp[i]表示出現的數字
		for (int j = 0; j < temp[i]; j++)   //j用來計數
			v[k++] = i;
	}
}

//6基數排序
void radixSort(vector<int> &v)
{
	int value_max = *max_element(v.begin(), v.end());
	int exp;
	for (exp = 1; value_max / exp>0; exp *= 10)     //開始排序,exp是位的個數
	{
		int bucket[10] = { 0 };     //10個桶，
		vector<int> output;
		output.resize(v.size());    //規定大小
		for (int i = 0; i < v.size(); i++)
		{
			bucket[(v[i]/exp)%10]++;
		}
		for (int i = 1; i < 10; i++)
		{
			bucket[i] += bucket[i - 1];
		}

		for (int i = v.size() - 1; i >= 0; i--)
		{
			output[bucket[(v[i] / exp) % 10] - 1] = v[i];
			bucket[(v[i] / exp) % 10]--;
		}
		for (int i = 0; i < v.size(); i++)
		{
			v[i] = output[i];
		}
	}
}

//7快速排序1,最後的數當作中間值，第一個數為基數值
void quickSort1(vector<int> &v,int begin, int end)
{
	if (begin >= end)
		return;
	int left = begin;
	int right = end;
	int temp = v[left];   //基數值
	while (left < right)
	{
		while (left < right && v[right] >= temp)  //從右側找到小于基數的值
			right--;
		if (left < right)   //找到之後，swap,right值轉到left,需要搜尋新值轉移到right
			v[left++] = v[right];
		while (left < right && v[left] <= temp)   //從左側開始找大于基數的值
		{
			left++;
		}
		if (left < right)
		{
			v[right--] = v[left];
		}
	}
	v[left] = temp;
	quickSort1(v,begin,left-1);
	quickSort1(v, left + 1, end);
}

//8歸并排序
//合并兩個有順序的數組
void merge(vector<int> &v, int begin, int mid, int end)   //合并
{
	vector<int> result;
	int i = begin, j = mid + 1;
	while (i <= mid && j <= end)
	{
		if (v[i] <= v[j])
		{
			result.push_back(v[i++]);
		}
		else
		{
			result.push_back(v[j++]);
		}
	}
	while (i <= mid)
	{
		result.push_back(v[i++]);
	}
	while (j <= end)
	{
		result.push_back(v[j++]);
	}
	for (int i = 0; i <result.size(); i++)
	{
		v[i+begin] = result[i];
	}
	result.clear();
	vector<int>().swap(result);
}
//歸并排序
void mergeSort(vector<int> &v, int begin, int end)   //歸并排序
{
	if (v.size() == 0 || begin >= end)
		return;
	int mid = (end + begin) / 2;
	mergeSort(v, begin, mid);
	mergeSort(v, mid + 1, end);

	merge(v, begin, mid, end);
}


//9希爾排序,i起始點，gap間隔,步長
void group_sort(vector<int> &v,int i,int gap)
{
	int len = v.size();
	for (int j = i + gap; j < len;j += gap)   //插入排序
	{
		int temp = v[j];
		int k;
		for (k = j - gap; k >= 0; k -= gap)
		{
			if (v[k] <= temp)
				break;
			v[k + gap] = v[k];
		}
		v[k + gap] = temp;
	}
}
void shellSort(vector<int> &v)
{
	int len = v.size();
	//gap為步長，每次減為
	for (int gap = len / 2; gap > 0; gap /= 2)
	{
		//進行排序le.選擇最小的
		for (int i = 0; i < gap; i++)
		{
			group_sort(v, i, gap);
		}
	}
}

//10堆排序,從小到大
//最大堆，向下調整，調整和父節點交換的子節點
void maxHeapDown(vector<int> &v,int begin, int end)
{
	int current_index = begin;
	for (int next_index = 2 * current_index + 1; next_index <= end; current_index = next_index, next_index = 2 * next_index + 1)
	{
		//next_index是左孩子，next_index+1是右孩子
		if (next_index < end && v[next_index] < v[next_index+1])   //如果右孩子大，換為右孩子
			next_index++;
		if (v[current_index] >= v[next_index])   //temp比較大，無操作
		{
			break;
		}
		else
		{
			int temp = v[current_index];
			v[current_index] = v[next_index];
			v[next_index] = temp;
		}
	}

}
void heapSort(vector<int> &v)
{
	//構造最大堆
	for (int i = v.size()/ 2 - 1; i >= 0; i--)
	{
		maxHeapDown(v,i, v.size()-1);
	}

	//得到從小到大的排序的數組,最後剩下的元素肯定是最小的
	for (int i = v.size() - 1; i > 0; i--)
	{
		int temp = v[0];   //調換順序
		v[0] = v[i];
		v[i] = temp;

		maxHeapDown(v, 0, i-1);
	}
}


//堆排序，從大到小
void minHeapDown(vector<int> &v, int begin, int end)
{
	int c = begin;

	for (int next = 2 * c + 1; next <= end; c = next, next = 2 * next + 1)   //l為左子節點
	{
		if (next<end && v[next]>v[next + 1])   //考慮了l=end的情況，這種情況直接過去;隻有當存在右結點而且右結點比較小的時候
			next++;
		if (v[c] <= v[next])
			break;
		else
		{
			int temp = v[c];
			v[c] = v[next];
			v[next] = temp;
		}
	}
}
void minHeapSort(vector<int> &v)
{
	//構造最小堆
	int len = v.size();
	for (int i = len / 2 - 1; i >= 0; i--)
	{
		minHeapDown(v,i, len-1);
	}
	
	for (int i = len - 1; i > 0; i--)
	{
		int temp = v[0];
		v[0] = v[i];
		v[i] = temp;
		minHeapDown(v,0,i-1);
	}
}

int main()
{
	vector<int> v;
	v.push_back(3);
	v.push_back(1);
	v.push_back(5);
	v.push_back(3);
	v.push_back(2);
	v.push_back(12);
	v.push_back(11);
	v.push_back(24);
	v.push_back(43);
	v.push_back(34);
	v.push_back(24);
	v.push_back(30);
	//bubbleSort(v);
	//seletionSort(v);
	//insertSort(v);
	//bucketSort(v, 2);
	//countSort(v);
	//radixSort(v);
	//quickSort1(v, 0, v.size()-1);
	//mergeSort(v, 0, v.size()-1);
	//shellSort(v);
	heapSort(v);
	//minHeapSort(v);

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << "  ";
	}

    return 0;
}