C语言基础入门知识——排序

排序的方法有很多种比较常见的便为:冒泡排序、选择排序、插入排序、快速排序。

今天我们就围绕着四种排序来说,如果有兴趣的话可以去查找一下其他排序。

在排序这方面我们主要讨论:

稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。空间复杂度:是指算法在计算机

一、冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法描述:冒泡排序主要比较相邻元素之间大小,从第一个元素开始比较,将较大的元素不断向后移动,然后重复此操作,注意最后一个元素不需此操作。

算法演示图:

代码实现:

void bulletSort(int arr[], int len)//冒泡排序

{

int temp = 0;//作为交换的中间变量

for (int i = 0; i

{

for (int j = 0; j

{

if (arr[j]>arr[j + 1])

{

temp = arr[j+1];

arr[j + 1] = arr[j];

arr[j] = temp;

}

}

}

}

二、选择排序

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

算法描述:定义一个变量min,然后从数组中找到最小值赋值给min,然后交换a[i]与min的值。

算法演示图:

void selectSort(int arr[], int len)

{

int min;

int temp = 0;

for (int i = 0; i

{

min = i;

for (int j = i + 1; j

{

if (arr[j]

min = j;

}

temp = arr[i];

arr[i] = arr[min];

arr[min] = temp;

}

}

如果大家对C语言感兴趣的话,可以关注我的弓众号:C语言进阶之旅 许多C语言资料免费给大家领取,如果大家有兴趣的话快来上车吧。

三、插入排序

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

算法描述:从第一个元素开发就已被标记,然后将后面一个作为交换元素,将如果后面一个元素小于前面一个元素的话,那么将元素不断的向左边移动。

算法演示图:

代码实现:

void insertSort(int arr[], int len)

{

int temp = 0;

int j = 0;

for (int i = 1; i

{

j = i - 1;

temp = arr[i];

while(j >= 0 && arr[j]>temp)

{

arr[j+1] = arr[j];

j--;

}

arr[j + 1] = temp;

}

}

四快速排序:

快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

算法描述:前面的三种排序相对于简单,后面这一种快速排序就得浪费点脑力了,快速排序由C. A. R. Hoare在1962年提出。快速排序是对冒泡排序的一种改进,采用了一种分治的策略。通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

算法演示图:

代码实现:

void quickSort(int arr[], int left, int right)

{

if (left >= right)return;

int i = left, j = right, temp;

while (i

{

while (i

j--;

while (i=arr[i])

i++;

if (i

{

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

}

//跳出循环则说明i==j

temp = arr[left];

arr[left] = arr[i];

arr[i] = temp;

quickSort(arr, left, i - 1);

quickSort(arr, i+1, right);

}

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20191014A0PUME00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券