找回网站备案密码,品牌策划案模板,专业seo培训,提供网站建设服务的网站排序的方法有很多种比较常见的便为#xff1a;冒泡排序、选择排序、插入排序、快速排序。
今天我们就围绕着四种排序来说#xff0c;如果有兴趣的话可以去查找一下其他排序。
在排序这方面我们主要讨论#xff1a;
稳定#xff1a;如果a原本在b前面#xff0c;而ab冒泡排序、选择排序、插入排序、快速排序。
今天我们就围绕着四种排序来说如果有兴趣的话可以去查找一下其他排序。
在排序这方面我们主要讨论
稳定如果a原本在b前面而ab排序之后a仍然在b的前面。不稳定如果a原本在b的前面而ab排序之后 a 可能会出现在 b 的后面。时间复杂度对排序数据的总的操作次数。反映当n变化时操作次数呈现什么规律。空间复杂度是指算法在计算机
一、冒泡排序
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列一次比较两个元素如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法描述冒泡排序主要比较相邻元素之间大小从第一个元素开始比较将较大的元素不断向后移动然后重复此操作注意最后一个元素不需此操作。
算法演示图 代码实现
void bulletSort(int arr[], int len)//冒泡排序
{int temp 0;//作为交换的中间变量for (int i 0; i (len - 1); i){for (int j 0; j ( len-i-1); j){if (arr[j]arr[j 1]){temp arr[j1];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 len - 1; i){min i;for (int j i 1; j len; j){if (arr[j]arr[min])min j;}temp arr[i];arr[i] arr[min];arr[min] temp;}
}
三、插入排序
插入排序Insertion-Sort的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。
算法描述从第一个元素开发就已被标记然后将后面一个作为交换元素将如果后面一个元素小于前面一个元素的话那么将元素不断的向左边移动。
算法演示图 代码实现
void insertSort(int arr[], int len)
{int temp 0;int j 0;for (int i 1; i len; i){j i - 1;temp arr[i];while(j 0 arr[j]temp){arr[j1] 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 j){while (i jarr[left] arr[j])j--;while (ijarr[left]arr[i])i;if (i j){temp arr[i];arr[i] arr[j];arr[j] temp;}}//跳出循环则说明ijtemp arr[left];arr[left] arr[i];arr[i] temp;quickSort(arr, left, i - 1);quickSort(arr, i1, right);
}
