【C++程式設計基礎】#003 排序算法：選擇排序、插入排序、冒泡排序、歸并排序。

問題描述

排序是算法與資料結構中比較基礎的一部分，本文利用C++語言，為大家介紹四種基礎實用的排序算法：

1. 冒泡排序 bubbleSort
2. 選擇排序 selectSort
3. 插入排序 insertSort
4. 歸并排序 mergeSort

小夥伴們需要自取，有幫助的話可以點個贊~

注：本文中提供的代碼均為完整代碼，放入C++工程後可直接運作。

代碼實作

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

void bubbleSort(int[],int);
void selectSort(int[], int);
void insertSort(int[], int);
void merge(int[], int, int, int);
void mergeSort(int[], int, int);
const int max = 500000;
int L[max / 2 + 2];
int R[max / 2 + 2];

int main()
{
	const int arraySize = 10;
	int a[arraySize] = { 7,5,8,9,6,3,2,1,4,6 };

	//bubbleSort(a, arraySize);
	
	for (int i = 0; i < arraySize; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;

	//electSort(a, arraySize);

	for (int i = 0; i < arraySize; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;

	//insertSort(a, arraySize);

	for (int i = 0; i < arraySize; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;



	mergeSort(a, 0, arraySize);
	for (int i = 0; i < arraySize; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;

	system("pause");
	return 0;
}


void bubbleSort(int a[],int size)
{
	int temp;
	
	for (int i = 0; i < size-1;i++)
	{
		for (int j = 0; j < size - 1 - i; j++)
		{
			if (a[j] > a[j+1])
			{
				temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
			}
		}
	}
}


void selectSort(int a[], int length)
{
	//每次都可以保證目前最小的數排在最前面
	int smallest;
	for (int i = 0; i < length-1; i++)
	{
		smallest = a[i];
		for (int j = i + 1; j < length; j++)
		{
			if (smallest > a[j])
			{
				smallest = a[j];
				a[j] = a[i];
				a[i] = smallest;
			}
		}
	}
}

void insertSort(int a[], int size)
{
	int temp;
	//每次循環後前i個數都是升序的，對後面的新加入的數看要插入到哪裡。
	for (int i = 1; i < size; i++)
	{
		for (int j = i; j > 0 &&a[j - 1] > a[j]; j--)
		{
			temp = a[j - 1];
			a[j - 1] = a[j];
			a[j] = temp;
		}
	}
}

void mergeSort(int a[],int left, int right)
{
	if (left + 1<right)
	{
		int mid = (left + right) / 2;
		mergeSort(a, left, mid);
		mergeSort(a, mid, right);
		merge(a, left, mid, right);
	}
	
}

void merge(int a[], int left, int mid,int right)
{
	int n1 = mid - left;
	int n2 = right - mid;
	for (int i = 0; i < n1; i++)
		L[i] = a[left + i];
	for (int i = 0; i < n2; i++)
		R[i] = a[mid + i];
	L[n1] = max;
	R[n2] = max;

	int i = 0;
	int j = 0;
	for (int k = left; k < right; k++)
	{
		if (L[i] <= R[j])
		{
			a[k] = L[i++];
		}
		else
		{
			a[k] = R[j++];
		}
	}

}