当前位置: 首页 > 编程笔记 >

c语言5个常用的排序算法实例代码

鄢飞鸾
2023-03-14
本文向大家介绍c语言5个常用的排序算法实例代码,包括了c语言5个常用的排序算法实例代码的使用技巧和注意事项,需要的朋友参考一下

1.插入排序

基本思想:插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕。

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.希尔排序

基本思想:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。

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.堆排序

用一句概括,堆排序就是一种改进的选择排序,改进的地方在于,每次做选择的时候,不单单把最大的数字选择出来,而且把排序过程中的一些操作进行了记录,这样在后续排序中可以利用,并且有分组的思想在里面,从而提高了排序效率,其效率为O(n*logn).

#include<stdio.h> 
int c=0;
/*heapadjust()函数的功能是实现从a[m]到a[n]的数据进行调整,使其满足大顶堆的特性*/
/*a[]是待处理的数组,m是起始坐标, n是终止坐标*/
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的值就是最大孩子的下标值 
		{
			i++;
		}
		if(a[i]<temp)//如果最大的孩子小于temp,则不做任何操作,退出循环;否则交换a[m]和a[i]的值,将最大值放到a[i]处 
		{
			break;
		}
		a[m]=a[i];
		m=i;
	}
	a[m]=temp;
}
void crtheap(int a[], int n)//初始化创建一个大顶堆 
{
	int i;
	for (i=n/2; i>0; i--)//n/2为最后一个双亲节点,依次向前建立大顶堆 
	{
		heapadjust(a, i, n);
	}
}
/*swap()函数的作用是将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);
		//将第一个数,也就是从a[1]到a[i]中的最大的数,放到a[i]的位置 
		heapadjust(a, 1, i-1);
		//对剩下的a[1]到a[i],再次进行堆排序,选出最大的值,放到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共交换数据%d次\n\n", c);
	printf("排序后:");
	for (i=1;i<10;i++) 
	{
		printf("%d",a[i]);
	}
	printf("\n\n\n");
	return 0;
}

4.归并排序

基本思想:归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列,归并排序包括两个步骤,分别为:

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);
  }
};

总结

以上就是本文关于c语言5个常用的排序算法实例代码的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

 类似资料:
  • 本文向大家介绍C语言实现九大排序算法的实例代码,包括了C语言实现九大排序算法的实例代码的使用技巧和注意事项,需要的朋友参考一下 直接插入排序 将数组分为两个部分,一个是有序部分,一个是无序部分。从无序部分中依次取出元素插入到有序部分中。过程就是遍历有序部分,实现起来比较简单。 折半插入排序 折半插入再直接插入上有改进,用折半搜索替换遍历数组,在数组长度大时能够提升查找性能。其本质还是从无序部分取出

  • 本文向大家介绍C语言实现冒泡排序算法,包括了C语言实现冒泡排序算法的使用技巧和注意事项,需要的朋友参考一下 BubblSort.c 以上所述就是本文的全部内容了,希望对大家学习C语言能够有所帮助。

  • 本文向大家介绍C语言实现的PNPoly算法代码例子,包括了C语言实现的PNPoly算法代码例子的使用技巧和注意事项,需要的朋友参考一下 写C语言的实验用到的一个算法,判断一个点是否在多边形的内部。C的代码如下: 其中nvert是多边形顶点的个数,vertx和verty分别是多边形顶点横、纵坐标的数组,textx和testy是待测点的坐标。这个算法是由W. Randolph Franklin提出的,

  • 本文向大家介绍C语言 选择排序算法详解及实现代码,包括了C语言 选择排序算法详解及实现代码的使用技巧和注意事项,需要的朋友参考一下 选择排序是排序算法的一种,这里以从小到大排序为例进行讲解。 基本思想及举例说明 选择排序(从小到大)的基本思想是,首先,选出最小的数,放在第一个位置;然后,选出第二小的数,放在第二个位置;以此类推,直到所有的数从小到大排序。 在实现上,我们通常是先确定第i小的数所在的

  • 本文向大家介绍Python实现的几个常用排序算法实例,包括了Python实现的几个常用排序算法实例的使用技巧和注意事项,需要的朋友参考一下 前段时间为准备百度面试恶补的东西,虽然最后还是被刷了,还是把那几天的“战利品”放点上来,算法一直是自己比较薄弱的地方,以后还要更加努力啊。 下面用Python实现了几个常用的排序,如快速排序,选择排序,以及二路并归排序等等。 运行结果如下:

  • 本文向大家介绍go语言睡眠排序算法实例分析,包括了go语言睡眠排序算法实例分析的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了go语言睡眠排序算法。分享给大家供大家参考。具体分析如下: 睡眠排序算法是一个天才程序员发明的,想法很简单,就是针对数组里的不同的数开多个线程,每个线程根据数的大小睡眠,自然睡的时间越长的,数越大,哈哈,搞笑吧,这种算法看起来很荒唐,但实际上很天才,它可以充分利用多