赞
踩
参考C++算法,这里面有些写法也值得商榷。
冒泡排序算法代码和思路比较简单,大家如果在面试时被要求实现排序时,可以用这种方法来实现。
该算法里,会统一地遍历待排序的数据,每次比较两个相邻的数据,如果它们顺序错误,比如要求是降序,但它们是升序,就交换这两个数据。
- // 冒泡排序改进(C++)
- void bubble_sort(int arr[], int len)
- {
- for (int i = len-1; i > 0; i--)
- {
- bool bExchange = false;
- for (int j = 0; j < i; j++)
- {
- if (arr[j] > arr[j + 1])
- {
- bExchange = true;
- swap(arr[j], arr[j + 1]);
- }
- }
- if(!Exchange)
- {
- break;
- }
- }
- }
在相邻数据一样时不会交换位置,所以冒泡排序是稳定的。
选择排序(Selection sort)是一种简单直观的排序算法。
选择排序的思想其实和冒泡排序有点类似,都是在一次排序后把最小的元素放到最前面,或者将最大值放在最后面。但是过程不同,冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择,每一趟从前往后查找出无序区最小值,将最小值交换至无序区最前面的位置。
① 第一轮从下标为 1 到下标为 n-1 的元素中选取最小值,若小于第一个数,则交换
② 第二轮从下标为 2 到下标为 n-1 的元素中选取最小值,若小于第二个数,则交换
③ 依次类推下去……
- template<typename T>
- void SlectionSort(T arr[], int len)
- {
- int i, j, min, temp;
- for(i = 0; i < len -1; i++)
- {
- int min = i;
- for(j = i + 1; j < len; j++)
- {
- if(arr[j] < arr[min])
- {
- min = j;
- }
- }
- temp = arr[min];
- arr[min] = arr[i];
- arr[i] = temp;
- }
- }
基于数组实现的选择排序是不稳定的,但基于链表实现的是稳定的。
不过排序算法一般是基于数组的,所以排序算法一般是不稳定的。
插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。打过扑克牌的应该都会明白(当然,如果你说你打扑克牌摸牌的时候从来不按牌的大小整理牌,那我只能呵呵了)
插入排序的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
① 从第一个元素开始,该元素可以认为已经被排序
② 取出下一个元素,在已经排序的元素序列中从后向前扫描
③如果该元素(已排序)大于新元素,将该元素移到下一位置
④ 重复步骤③,直到找到已排序的元素小于或者等于新元素的位置
⑤将新元素插入到该位置后
⑥ 重复步骤②~⑤
- void InsertionSort(int[] arr, int len)
- {
- for (int i = 1; i < len; i++)
- {
- int val = arr[i];
- int pos = i;
- while (pos > 0 && arr[pos-1] > val)
- {
- arr[pos] = arr[pos-1];
- pos--;
- }
- arr[pos] = val;
- }
- }
由于只需要找到不大于当前数据的位置,所以相同的数据不需交换,所以插入排序是稳定。
归并排序,是创建在归并操作上的一种有效的排序算法。算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。归并排序思路简单,速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列。
归并排序是用分治思想,分治模式在每一层递归上有三个步骤:
① 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
② 设定两个指针,最初位置分别为两个已经排序序列的起始位置
③ 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
④ 重复步骤③直到某一指针到达序列尾
⑤ 将另一序列剩下的所有元素直接复制到合并序列尾
① 将序列每相邻两个数字进行归并操作,形成floor(n/2)个序列,排序后每个序列包含两个元素
② 将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素
③ 重复步骤②,直到所有元素排序完毕
- / 归并排序(C++-迭代版)
- template<typename T>
- void merge_sort(T arr[], int len) {
- T* a = arr;
- T* b = new T[len];
- for (int seg = 1; seg < len; seg += seg) {
- for (int start = 0; start < len; start += seg + seg) {
- int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
- int k = low;
- int start1 = low, end1 = mid;
- int start2 = mid, end2 = high;
- while (start1 < end1 && start2 < end2)
- b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
- while (start1 < end1)
- b[k++] = a[start1++];
- while (start2 < end2)
- b[k++] = a[start2++];
- }
- T* temp = a;
- a = b;
- b = temp;
- }
-
- if (a != arr) {
- for (int i = 0; i < len; i++)
- b[i] = a[i];
- b = a;
- }
-
- delete[] b;
- }
- tamplate<typename T>
- void MergeSortRecursive(T arr[], T reg[], int start, int end)
- {
- if(start >= end)
- return;
- int len = end - start;
- int mid = (len >>1) + start;
- int start1 = start, end1 = mid;
- int start2 = mid + 1, end2 = end;
- MergeSortRecursive(arr, reg, start1, end1);
- MergeSortRecursive(arr, reg, start2, end2);
-
- int k = start;
- while(start1 <= end1 && start2 <= end2)
- reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++]
- while(start1 <= end1)
- reg[k++] = arr[start1++];
- while(start2 < end2)
- reg[k++] = arr[start2++];
- for(k = start; k < end, k++)
- arr[k] = reg[k];
- }
-
- template<typename T>
- void MergSort(T arr[], const int len)
- {
- T reg[len];
- MergeSortRecursive(arr, reg, 0, len -1);
- }
因为遇到相等的数据时,是按顺序放在辅助的子序列里,所以,归并排序是稳定的。
快速排序在大数据情况下性能比较优秀,而且实现比较简单,所以也有比较广泛的应用。
- void quickSort(int a[], int low ,int high)
- {
- if(low<high) //判断是否满足排序条件,递归的终止条件
- {
- int i = low, j = high; //把待排序数组元素的第一个和最后一个下标分别赋值给i,j,使用i,j进行排序;
- int x = a[low]; //将待排序数组的第一个元素作为哨兵,将数组划分为大于哨兵以及小于哨兵的两部分
- while(i<j)
- {
- while(i<j && a[j] >= x) j--; //从最右侧元素开始,如果比哨兵大,那么它的位置就正确,然后判断前一个元素,直到不满足条件
- if(i<j) a[i++] = a[j]; //把不满足位次条件的那个元素值赋值给第一个元素,(也即是哨兵元素,此时哨兵已经保存在x中,不会丢失)并把i的加1
- while(i<j && a[i] <= x) i++; //换成左侧下标为i的元素开始与哨兵比较大小,比其小,那么它所处的位置就正确,然后判断后一个,直到不满足条件
- if(i<j) a[j--] = a[i]; //把不满足位次条件的那个元素值赋值给下标为j的元素,(下标为j的元素已经保存到前面,不会丢失)并把j的加1
- }
- a[i] = x; //完成一次排序,把哨兵赋值到下标为i的位置,即前面的都比它小,后面的都比它大
- quickSort(a, low ,i-1); //递归进行哨兵前后两部分元素排序 , low,high的值不发生变化,i处于中间
- quickSort(a, i+1 ,high);
- }
- }
由于在算法实现过程中无法保证相等的数据按顺序被扫描和按顺序存放,所以该算法不是稳定的。
在希尔排序算法出现前,计算机界普遍存在“排序算法不可能突破O(n平方)”的观点。希尔排序是第一个突破O(n平方)的排序算法,它是简单插入排序的改进版。希尔排序主要基于以下两点:
先将整个待排序的记录序列拆分成为若干子序列,再分别进行直接插入排序,具体算法描述:
- public static void shellSort(int[] arr){
- int delta = 1;
- while (delta < arr.length/3){//generate delta
- delta=delta*3+1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
- }
- int temp;
- for (; delta>=1; delta/=3){
- for (int i=delta; i<arr.length; i++){
- for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){
- temp = arr[j-delta];
- arr[j-delta] = arr[j];
- arr[j] = temp;
- }
- }//loop i
- }//loop delta
- }
希尔排序的增量数列可以任取,需要的唯一条件是最后一个一定为1(因为要保证按1有序)。但是,不同的数列选取会对算法的性能造成极大的影响。
下面是一些常见的增量序列。
第一种增量是最初Donald Shell提出的增量,即折半降低直到1。据研究,使用希尔增量,其时间复杂度还是O(n平方)。
第二种增量Hibbard:{1, 3, ..., 2k-1}。该增量序列的时间复杂度大约是O(n的1.5次方)。
第三种增量Sedgewick增量:(1, 5, 19, 41, 109,...),其生成序列或者是94i - 92i + 1或者是4i - 3*2i + 1。
插入排序是稳定算法。但是,Shell排序是一个多次插入的过程。在一次插入中能确保不移动相同元素的顺序,但在多次的插入中,相同元素完全有可能在不同的插入轮次被移动,最后稳定性被破坏,因此,该排序排序不是一个稳定的算法。
计数排序不是基于比较的排序算法,它的核心做法是,把输入的数据值转化为键存储在新开辟的数组里。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。
- public static void countSort(int[] a, int max, int min) {
- int[] b = new int[a.length];//存储数组
- int[] count = new int[max - min + 1];//计数数组
-
- for (int num = min; num <= max; num++) {
- //初始化各元素值为0,数组下标从0开始因此减min
- count[num - min] = 0;
- }
-
- for (int i = 0; i < a.length; i++) {
- int num = a[i];
- count[num - min]++;//每出现一个值,计数数组对应元素的值+1
- }
-
- for (int num = min + 1; num <= max; num++) {
- //加总数组元素的值为计数数组对应元素及左边所有元素的值的总和
- count[num - min] += sum[num - min - 1]
- }
-
- for (int i = 0; i < a.length; i++) {
- int num = a[i];//源数组第i位的值
- int index = count[num - min] - 1;//加总数组中对应元素的下标
- b[index] = num;//将该值存入存储数组对应下标中
- count[num - min]--;//加总数组中,该值的总和减少1。
- }
-
- //将存储数组的值一一替换给源数组
- for(int i=0;i<a.length;i++){
- a[i] = b[i];
- }
- }
该排序算法是稳定的。
桶排序是计数排序的升级版,其工作原理是将数组分到有限数量的桶子里,然后对每个桶子再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序),最后将各个桶中的数据有序的合并起来。
如下能看到大致的过程。
桶排序
- public static void bucketSort(int[] arr){
- int max = Integer.MIN_VALUE;
- int min = Integer.MAX_VALUE;
- for(int i = 0; i < arr.length; i++){
- max = Math.max(max, arr[i]);
- min = Math.min(min, arr[i]);
- }
- //桶数
- int bucketNum = (max - min) / arr.length + 1;
- ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
- for(int i = 0; i < bucketNum; i++){
- bucketArr.add(new ArrayList<Integer>());
- }
- //将每个元素放入桶
- for(int i = 0; i < arr.length; i++){
- int num = (arr[i] - min) / (arr.length);
- bucketArr.get(num).add(arr[i]);
- }
- //对每个桶进行排序
- for(int i = 0; i < bucketArr.size(); i++){
- Collections.sort(bucketArr.get(i));
- }
- System.out.println(bucketArr.toString());
- }
可以看到在分桶和从桶依次输出的过程是稳定的。但是由于在对每个桶进行排序时使用了其他算法,所以,桶排序的稳定性依赖于这些算法的稳定性,比如在对每个桶进行排序时用到了快速排序法等不稳定的算法时,整个桶排序算法就不是不稳定的。
基数排序(Radix Sort)是桶排序的扩展,其基本思想是:把整数按位数切割成不同的数字,然后按每个位数分别比较。
排序过程是,把所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面的位数补零,随后从最低位开始,依次进行一次排序。这样从最低位一直到最高位排序完成后,该数列就成了一个有序的序列。
- public abstract class Sorter {
- public abstract void sort(int[] array);
- }
-
- public class RadixSorter extends Sorter {
-
- private int radix;
-
- public RadixSorter() {
- radix = 10;
- }
-
- @Override
- public void sort(int[] array) {
- // 数组的第一维表示可能的余数0-radix,第二维表示array中的等于该余数的元素
- // 如:十进制123的个位为3,则bucket[3][] = {123}
- int[][] bucket = new int[radix][array.length];
- int distance = getDistance(array); // 表示最大的数有多少位
- int temp = 1;
- int round = 1; // 控制键值排序依据在哪一位
- while (round <= distance) {
- // 用来计数:数组counter[i]用来表示该位是i的数的个数
- int[] counter = new int[radix];
- // 将array中元素分布填充到bucket中,并进行计数
- for (int i = 0; i < array.length; i++) {
- int which = (array[i] / temp) % radix;
- bucket[which][counter[which]] = array[i];
- counter[which]++;
- }
- int index = 0;
- // 根据bucket中收集到的array中的元素,根据统计计数,在array中重新排列
- for (int i = 0; i < radix; i++) {
- if (counter[i] != 0)
- for (int j = 0; j < counter[i]; j++) {
- array[index] = bucket[i][j];
- index++;
- }
- counter[i] = 0;
- }
- temp *= radix;
- round++;
- }
- }
-
- private int getDistance(int[] array) {
- int max = computeMax(array);
- int digits = 0;
- int temp = max / radix;
- while(temp != 0) {
- digits++;
- temp = temp / radix;
- }
- return digits + 1;
- }
-
- private int computeMax(int[] array) {
- int max = array[0];
- for(int i=1; i<array.length; i++) {
- if(array[i]>max) {
- max = array[i];
- }
- }
- return max;
- }
- }
通过上面的排序过程可以看到,每一轮操作,都按从左到右的顺序进行,如果出现相同的元素,则会保持它们在原始数组中的顺序。所以基数排序是一种稳定的排序。
最后再整理下各算法的时间和空间复杂度,以及它们的稳定性。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。