c語言5個(gè)常用的排序算法實(shí)例代碼

2020-01-26 13:46:18

字體：大中小

供稿：網(wǎng)友

1.插入排序

基本思想：插入排序就是每一步都將一個(gè)待排數(shù)據(jù)按其大小插入到已經(jīng)排序的數(shù)據(jù)中的適當(dāng)位置，直到全部插入完畢。

void insertSort(vector<int>& nums){  int k = 0;  for (int i = 0; i < nums.size(); ++i)  {    int temp = nums[i];    int j = i;    for (; j > 0 && temp < nums[j-1]; --j)      nums[j] = nums[j-1];    nums[j] = temp;  }}

2.希爾排序

基本思想：先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序，待整個(gè)序列中的元素基本有序（增量足夠小）時(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況），效率是很高的，因此希爾排序在時(shí)間效率上比前兩種方法有較大提高。

void shellSort(vector<int>& nums){  for (int gap = nums.size() / 2; gap > 0; gap /= 2)  {    for (int i = gap; i < nums.size(); ++i)    {      int temp = nums[i];      int j = i;      for (; j >=gap && temp < nums[j-gap]; j -= gap)        nums[j] = nums[j - gap];      nums[j] = temp;    }  }}

3.堆排序

用一句概括，堆排序就是一種改進(jìn)的選擇排序，改進(jìn)的地方在于，每次做選擇的時(shí)候，不單單把最大的數(shù)字選擇出來，而且把排序過程中的一些操作進(jìn)行了記錄，這樣在后續(xù)排序中可以利用，并且有分組的思想在里面，從而提高了排序效率，其效率為O(n*logn).

#include<stdio.h> int c=0;/*heapadjust()函數(shù)的功能是實(shí)現(xiàn)從a[m]到a[n]的數(shù)據(jù)進(jìn)行調(diào)整，使其滿足大頂堆的特性*//*a[]是待處理的數(shù)組，m是起始坐標(biāo)， n是終止坐標(biāo)*/void heapadjust(int a[], int m, int n) {	int i, temp;	temp=a[m];	for (i=2*m;i<=n;i*=2)//從m的左孩子開始 	{		if(i+1<=n && a[i]<a[i+1])//如果左孩子小于右孩子，則將i++，這樣i的值就是最大孩子的下標(biāo)值 		{			i++;		}		if(a[i]<temp)//如果最大的孩子小于temp，則不做任何操作，退出循環(huán)；否則交換a[m]和a[i]的值，將最大值放到a[i]處 		{			break;		}		a[m]=a[i];		m=i;	}	a[m]=temp;}void crtheap(int a[], int n)//初始化創(chuàng)建一個(gè)大頂堆 {	int i;	for (i=n/2; i>0; i--)//n/2為最后一個(gè)雙親節(jié)點(diǎn)，依次向前建立大頂堆 	{		heapadjust(a, i, n);	}}/*swap()函數(shù)的作用是將a[i]和a[j]互換*/void swap(int a[], int i, int j) {	int temp;	temp=a[i];	a[i]=a[j];	a[j]=temp;	c++;}void heapsort(int a[], int n) {	int i;	crtheap(a, n);	for (i=n; i>1; i--) 	{		swap(a, 1, i);		//將第一個(gè)數(shù)，也就是從a[1]到a[i]中的最大的數(shù)，放到a[i]的位置 		heapadjust(a, 1, i-1);		//對(duì)剩下的a[1]到a[i]，再次進(jìn)行堆排序，選出最大的值，放到a[1]的位置	}}int main(void) {	int i;	int a[10]={-1,5,2,6,0,3,9,1,7,4};	printf("排序前：");	for (i=1;i<10;i++) 	{		printf("%d",a[i]);	}	heapsort(a, 9);	printf("/n/n共交換數(shù)據(jù)%d次/n/n", c);	printf("排序后：");	for (i=1;i<10;i++) 	{		printf("%d",a[i]);	}	printf("/n/n/n");	return 0;}

4.歸并排序

基本思想：歸并排序是利用遞歸和分而治之的技術(shù)將數(shù)據(jù)序列劃分成為越來越小的半子表，再對(duì)半子表排序，最后再用遞歸步驟將排好序的半子表合并成為越來越大的有序序列，歸并排序包括兩個(gè)步驟，分別為：

1）劃分子表
2）合并半子表

剛好最近刷leetcode有道題用的歸并排序：sort list

class Solution {public: //歸并排序  ListNode* getMiddleOfList(ListNode* head)  {    ListNode* mid = head;    ListNode* last = head;    while (last->next!=NULL&&last->next->next!=NULL)    {      mid = mid->next;      last = last->next->next;    }    return mid;  }  ListNode* sortList(ListNode* head) {    if (head == NULL || head->next == NULL)return head;    ListNode* mid = getMiddleOfList(head);    ListNode* midnext = mid->next;    mid->next = NULL;    return mergeList(sortList(head), sortList(midnext));  }  ListNode* mergeList(ListNode* a, ListNode* b)  {    ListNode* res = new ListNode(-1);    ListNode* cur = res;    while (a != NULL&&b != NULL)    {      if (a->val < b->val)      {        cur->next = a;        a = a->next;      }      else      {        cur->next = b;        b = b->next;      }      cur = cur->next;    }    cur->next = a != NULL ? a : b;    return res->next;  }};

5.快速排序

class sort {public:  int median3(vector<int>& nums, int left, int right)  {    int mid = (left + right) / 2;    if (nums[left] > nums[mid])swap(nums[left], nums[mid]);    if (nums[mid] > nums[right])swap(nums[mid], nums[right]);    if (nums[left] > nums[mid])swap(nums[left], nums[mid]);    swap(nums[mid], nums[left]);    return nums[left];  }  void quickSort(vector<int>& nums, int i, int j)  {    if (i > j)return;    int partition = median3(nums, i, j);    int low = i+1, high = j;    while (low < high)    {      while (nums[low] < partition)low++;           while (nums[high] > partition)high--;      if (low < high)swap(nums[low], nums[high]);      else        break;    }    swap(nums[i], nums[high]);    quickSort(nums, i, high - 1);    quickSort(nums, high + 1, j);  }  void qs(vector<int>& nums)  {    quickSort(nums, 0, nums.size() - 1);  }};