常見(jiàn)的排序算法

   排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無(wú)序”的記錄序列調(diào)整為“有序”的記錄序。   

    常見(jiàn)的排序算法：冒泡、快排、插入、希爾、選擇、堆排、歸并。

1、冒泡排序

原理：一個(gè)無(wú)序數(shù)組，按照升序排列。int i 代表循環(huán)的次數(shù)，int j 代表數(shù)組的下標(biāo)，if(arr[j]>arr[j+1]),交換位置，依次類(lèi)推。每循環(huán)一次，一個(gè)數(shù)字在它相應(yīng)的位置。

源碼：

void Bubble_sort(int arr[],int len)
{
	int i;
	for(i=0;i<len;i++)
	{
		int j;
		for(j=0;j<len-1-i;j++)
		{
			if(arr[j]>arr[j+1])
			{
				int tmp=arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=tmp;
			}
		}
	}
}

時(shí)間復(fù)雜度o(n^2),空間復(fù)雜度o(1).

2、快排：

原理：從中間向兩邊的探索，在序列中選擇一個(gè)準(zhǔn)基數(shù)，用來(lái)做參考的數(shù)，選擇左邊的第一個(gè)數(shù)為例，將序列中所有大于準(zhǔn)基數(shù)的數(shù)放在它的右邊，小于的放在它的左邊，最終確定準(zhǔn)基數(shù)的位置。

定義兩個(gè)變量left、right，可以將其看作指針，指定其對(duì)應(yīng)的某元素，一個(gè)指向最左邊，一個(gè)指向最右邊，選擇left作為準(zhǔn)基數(shù)，從最左邊的數(shù)和它比較，當(dāng)準(zhǔn)基數(shù)小于right指向的數(shù)時(shí)，right--，如果大于right指向的數(shù)，arr[left]=arr[right],當(dāng)準(zhǔn)基數(shù)大于左邊的值時(shí)，left++，如果小于左邊的值，arr[right]=arr[left],最后將準(zhǔn)基數(shù)放在其正確的位置，然后重復(fù)上述步驟遞歸。

源碼：

void Quick_sort(int arr[],int Front,int Back)
{
	int left=Front;
	int right=Back;
	if (left < right)
	{
		int tmp = arr[left];
		while(left<right)
		{
			while (left < right && tmp < arr[right])
			{
				right--;
			}
			arr[left] = arr[right];
			while (left < right && tmp > arr[left])
			{
				left++;
			}
			arr[right] = arr[left];
		}
		arr[left] = tmp;
		Quick_sort(arr,Front,left-1);
		Quick_sort(arr,left+1,Back);
	}
}

時(shí)間復(fù)雜度o(nlog2n),空間復(fù)雜度o(nlog2n)

3、插入排序：

原理：插入排序就是講一個(gè)數(shù)字插入到它本該占據(jù)的位置。

源碼：

void Insertsort(int arr[],int len)
{
	int i = 0;
	for (i = 0; i < len-1; i++)
	{
		int tmp = arr[i+1];
		int pos = i;
		while (pos>=0 && arr[pos] > tmp)
		{
			arr[pos+1] = arr[pos];
			pos--;
		}
		arr[pos+1] = tmp;
	}
}

時(shí)間復(fù)雜度o(n^2),空間復(fù)雜度o(1).

4、希爾排序

原理：希爾排序就是基于插入排序的一種改進(jìn)，先將整個(gè)待排元素分成若干個(gè)子序列（有相隔某個(gè)增量元素組成），分別進(jìn)行插入排序，然后縮減增量再進(jìn)行排序，待這整個(gè)元素基本有序時(shí)（增量足夠小），再對(duì)全體元素進(jìn)行一次插入排序。

源碼：

void ShellSort(int arr[], int len)
{
	int gap = len;
	while (gap)
	{
		gap = gap/2;
		for (int i = gap; i < len; i++)
		{
			int tmp = arr[i];
			int pos = i-gap;
			while (pos>=0 && arr[pos] > tmp)
			{
				arr[pos+gap] = arr[pos];
				pos-=gap;
			}
			arr[pos+gap] = tmp;
		}
	}
}

時(shí)間復(fù)雜度o(n^2),空間復(fù)雜度o(1).

5、選擇排序

原理：在待排序列中將第一個(gè)元素記為最小的，第一個(gè)位置記為最小位置，在剩余所有元素中找到最小的與之交換。

源碼：

void SelectSort(int arr[], int len)
{
	for (int i = 0; i < len; i++)
	{
		int min = arr[i];
		int index = i;
		for (int j = i+1; j < len; j++)
		{
			if(arr[j] < min)
			{
				min = arr[j];
				index = j;
			}
		}
		arr[index] = arr[i];
		arr[i] = min;
	}
}

時(shí)間復(fù)雜度o(n^2),空間復(fù)雜度o(1).

6、堆排

將初始化序列構(gòu)成大堆，此堆為初始的無(wú)序區(qū)，將堆頂元素與最后一個(gè)元素交換位置，得到一個(gè)無(wú)序區(qū)和一個(gè)有序區(qū)，交換后的堆頂元素不變，因此將堆頂元素向下調(diào)整，保證最大堆的性質(zhì)。

源碼：

void HeapDown(int arr[],int i,int len)
{
	int parent=i;
	int child=2*i+1;
	while (child < len)
	{
		if(child+1<len && arr[child]<arr[child+1])
		{
			child=child+1;
		}
		if(arr[child]>arr[parent])
		{
			swap(arr[parent],arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void CreateHeap(int arr[],int len)
{
	int i=0;
	for(i=len/2-1;i>=0;i--)
	{
		HeapDown(arr,i,len);
	}
}

void HeapSort(int arr[],int len)
{
	CreateHeap(arr,len);
	for (int i = len-1; i >= 0; i--)
	{
		swap(arr[0],arr[i]);
		HeapDown(arr,0,i);
	}
}

時(shí)間復(fù)雜度o(nlog2n),空間復(fù)雜度o(1).

7、歸并排序

源碼：

void MergeArray(int arr[], int low, int mid, int high,int a[])
{
	int i = low;
	int j = mid+1;
	int k = 0;
	while (i <= mid && j <= high)
	{
		if (arr[i] <= arr[j])
		{
			a[k] = arr[i];
			i++;
			k++;
		}
		else
		{
			a[k] = arr[j];
			j++;
			k++;
		}
	}
	while (i<=mid)
	{
		a[k] = arr[i];
		i++;
		k++;
	}
	while (j <= high)
	{
		a[k] = arr[j];
		j++;
		k++;
	}
	for (i = 0; i < k; i++)
	{
		arr[low+i] = a[i];
	}
}

void MSort(int arr[],int first, int last, int a[])
{
	if(first < last)
	{
		int mid = (first+last)/2;
		MSort(arr,first,mid,a);
		MSort(arr,mid+1,last,a);
		MergeArray(arr,first,mid,last,a);
	}
}

void Mergesort(int arr[], int sz)
{
	int *a = new int[sz];
	MSort(arr,0,sz-1,a);
	delete []a;
}

時(shí)間復(fù)雜度o(nlog2n),空間復(fù)雜度o(n)。