程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 插入排序、冒泡排序、選擇排序、希爾排序、快速排序、歸並排序、堆排序和LST基數排序——C++實現

插入排序、冒泡排序、選擇排序、希爾排序、快速排序、歸並排序、堆排序和LST基數排序——C++實現

編輯:C++入門知識

插入排序、冒泡排序、選擇排序、希爾排序、快速排序、歸並排序、堆排序和LST基數排序——C++實現


首先是算法實現文件Sort.h,代碼如下:

 

/*
* 實現了八個常用的排序算法:插入排序、冒泡排序、選擇排序、希爾排序
* 以及快速排序、歸並排序、堆排序和LST基數排序
* @author gkh178
*/
#include 

template
void swap_value(T &a, T &b)
{
	T temp = a;
	a = b;
	b = temp;
}

//插入排序:時間復雜度o(n^2)
template
void insert_sort(T a[], int n)
{
	for (int i = 1; i < n; ++i)
	{
		T temp = a[i];
		int j = i - 1;
		while (j >= 0 && a[j] > temp)
		{
			a[j + 1] = a[j];
			--j;
		}
		a[j + 1] = temp;
	}
}

//冒泡排序:時間復雜度o(n^2) 
template
void bubble_sort(T a[], int n)
{
	for (int i = n - 1; i > 0; --i)
	{
		for (int j = 0; j < i; ++j)
		{
			if (a[j] > a[j + 1])
			{
				swap_value(a[j], a[j + 1]);
			}
		}
	}
}

//選擇排序:時間復雜度o(n^2)
template
void select_sort(T a[], int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		T min = a[i];
		int index = i;
		for (int j = i + 1; j < n; ++j)
		{
			if (a[j] < min)
			{
				min = a[j];
				index = j;
			}
		}
		a[index] = a[i];
		a[i] = min;
	}
}

//希爾排序:時間復雜度介於o(n^2)和o(nlgn)之間 
template
void shell_sort(T a[], int n)
{
	for (int gap = n / 2; gap >= 1; gap /= 2)
	{
		for (int i = gap; i < n; ++i)
		{
			T temp = a[i];
			int j = i - gap;
			while (j >= 0 && a[j] > temp)
			{
				a[j + gap] = a[j];
				j -= gap;
			}
			a[j + gap] = temp;
		}
	}
}

//快速排序:時間復雜度o(nlgn)  
template
void quick_sort(T a[], int n)
{
	_quick_sort(a, 0, n - 1);
}
template
void _quick_sort(T a[], int left, int right)
{
	if (left < right)
	{
		int q = _partition(a, left, right);
		_quick_sort(a, left, q - 1);
		_quick_sort(a, q + 1, right);
	}
}
template
int _partition(T a[], int left, int right)
{
	T pivot = a[left];
	while (left < right)
	{
		while (left < right && a[right] >= pivot)
		{
			--right;
		}
		a[left] = a[right];
		while (left < right && a[left] <= pivot)
		{
			++left;
		}
		a[right] = a[left];
	}
	a[left] = pivot;
	return left;
}

//歸並排序:時間復雜度o(nlgn)  
template
void merge_sort(T a[], int n)
{
	_merge_sort(a, 0, n - 1);
}
template
void _merge_sort(T a[], int left, int right)
{
	if (left < right)
	{
		int mid = left + (right - left) / 2;
		_merge_sort(a, left, mid);
		_merge_sort(a, mid + 1, right);
		_merge(a, left, mid, right);
	}
}
template
void _merge(T a[], int left, int mid, int right)
{
	int length = right - left + 1;
	T *newA = new T[length];
	for (int i = 0, j = left; i <= length - 1; ++i, ++j)
	{
		*(newA + i) = a[j];
	}
	int i = 0;
	int j = mid - left + 1;
	int k = left;
	for (; i <= mid - left && j <= length - 1; ++k)
	{
		if (*(newA + i) < *(newA + j))
		{
			a[k] = *(newA + i);
			++i;
		}
		else
		{
			a[k] = *(newA + j);
			++j;
		}
	}
	while (i <= mid - left)
	{
		a[k++] = *(newA + i);
		++i;
	}
	while (j <= right - left)
	{
		a[k++] = *(newA + j);
		++j;
	}
	delete newA;
}

//堆排序:時間復雜度o(nlgn) 
template
void heap_sort(T a[], int n)
{
	built_max_heap(a, n);//建立初始大根堆  
	//交換首尾元素,並對交換後排除尾元素的數組進行一次上調整  
	for (int i = n - 1; i >= 1; --i)
	{
		swap_value(a[0], a[i]);
		up_adjust(a, i);
	}
}
//建立一個長度為n的大根堆  
template
void built_max_heap(T a[], int n)
{
	up_adjust(a, n);
}
//對長度為n的數組進行一次上調整  
template
void up_adjust(T a[], int n)
{
	//對每個帶有子女節點的元素遍歷處理,從後到根節點位置  
	for (int i = n / 2; i >= 1; --i)
	{
		adjust_node(a, n, i);
	}
}
//調整序號為i的節點的值  
template
void adjust_node(T a[], int n, int i)
{
	//節點有左右孩子  
	if (2 * i + 1 <= n)
	{
		//右孩子的值大於節點的值,交換它們  
		if (a[2 * i] > a[i - 1])
		{
			swap_value(a[2 * i], a[i - 1]);
		}
		//左孩子的值大於節點的值,交換它們  
		if (a[2 * i - 1] > a[i - 1])
		{
			swap_value(a[2 * i - 1], a[i - 1]);
		}
		//對節點的左右孩子的根節點進行調整  
		adjust_node(a, n, 2 * i);
		adjust_node(a, n, 2 * i + 1);
	}
	//節點只有左孩子,為最後一個有左右孩子的節點  
	else if (2 * i == n)
	{
		//左孩子的值大於節點的值,交換它們  
		if (a[2 * i - 1] > a[i - 1])
		{
			swap_value(a[2 * i - 1], a[i - 1]);
		}
	}
}

//基數排序的時間復雜度為o(distance(n+radix)),distance為位數,n為數組個數,radix為基數  
//本方法是用LST方法進行基數排序,MST方法不包含在內  
//其中參數radix為基數,一般為10;distance表示待排序的數組的數字最長的位數;n為數組的長度 
template
void lst_radix_sort(T a[], int n, int radix, int distance)
{
	T* newA = new T[n];//用於暫存數組  
	int* count = new int[radix];//用於計數排序,保存的是當前位的值為0 到 radix-1的元素出現的的個數  
	int divide = 1;
	//從倒數第一位處理到第一位  
	for (int i = 0; i < distance; ++i)
	{
		//待排數組拷貝到newA數組中
		for (int j = 0; j < n; ++j)
		{
			*(newA + j) = a[j];
		}
		//將計數數組置0  
		for (int j = 0; j < radix; ++j)
		{
			*(count + j) = 0;
		}
		for (int j = 0; j < n; ++j)
		{
			int radixKey = (*(newA + j) / divide) % radix; //得到數組元素的當前處理位的值  
			(*(count + radixKey))++;
		}
		//此時count[]中每個元素保存的是radixKey位出現的次數  
		//計算每個radixKey在數組中的結束位置,位置序號范圍為1-n  
		for (int j = 1; j < radix; ++j)
		{
			*(count + j) = *(count + j) + *(count + j - 1);
		}
		//運用計數排序的原理實現一次排序,排序後的數組輸出到a[]  
		for (int j = n - 1; j >= 0; --j)
		{
			int radixKey = (*(newA + j) / divide) % radix;
			a[*(count + radixKey) - 1] = newA[j];
			--(*(count + radixKey));
		}
		divide = divide * radix;
	}
}

然後是測試文件main.cpp,代碼如下:

 

 

#include Sort.h
using namespace std;

template
void printArray(T a[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		cout << a[i] <<  ;
	}
	cout << endl;
}

int main()
{
	for (int i = 1; i <= 8; ++i)
	{
		int arr[] = { 45, 38, 26, 77, 128, 38, 25, 444, 61, 153, 9999, 1012, 43, 128 };
		switch (i)
		{
		case 1:
			insert_sort(arr, sizeof(arr) / sizeof(arr[0]));
			break;
		case 2:
			bubble_sort(arr, sizeof(arr) / sizeof(arr[0]));
			break;
		case 3:
			select_sort(arr, sizeof(arr) / sizeof(arr[0]));
			break;
		case 4:
			shell_sort(arr, sizeof(arr) / sizeof(arr[0]));
			break;
		case 5:
			quick_sort(arr, sizeof(arr) / sizeof(arr[0]));
			break;
		case 6:
			merge_sort(arr, sizeof(arr) / sizeof(arr[0]));
			break;
		case 7:
			heap_sort(arr, sizeof(arr) / sizeof(arr[0]));
			break;
		case 8:
			lst_radix_sort(arr, sizeof(arr) / sizeof(arr[0]), 10, 4);
			break;
		default:
			break;
		}
		printArray(arr, sizeof(arr) / sizeof(arr[0]));
	}
	return 0;
}

最後是運行結果圖,如下:

 

\

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved