好贷网好贷款

排序算法

发布时间:2016-12-3 21:45:52 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"排序算法",主要涉及到排序算法方面的内容,对于排序算法感兴趣的同学可以参考一下。

/** 选择排序算法 原理:工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置, 然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。 以此类推,直到所有元素均排序完毕。 复杂度分析:选择排序的交换操作介于和次之间。选择排序的比较操作为次之间。选择排序的赋值操作介于和次之间。 比较次数O(n^2),比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。 交换次数O(n),最好情况是,已经有序,交换0次;最坏情况是,逆序,交换n-1次。 交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。 @param arr待排序数组 */ public static void sortSelect( int [] arr ) { for (int i=0; i<arr.length-1; i++ ) { for(int j=i+1; j<arr.length; j++) { if(arr[j] < arr[i]) { arr[j] = arr[i]^arr[j]; arr[i] = arr[i]^arr[j]; arr[j] = arr[i]^arr[j]; } } } } /** 完成冒泡排序 原理: 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。 针对所有的元素重复以上的步骤,除了最后一个。 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 由于它的简洁,冒泡排序通常被用来对于程式设计入门的学生介绍算法的概念。 复杂度分析:冒泡排序对个项目需要O()的比较次数,且可以原地排序。尽管这个算法是最简单了解和实作的排序算法之一, 但它对于少数元素之外的数列排序是很没有效率的。 冒泡排序是与插入排序拥有相等的执行时间,但是两种法在需要的交换次数却很大地不同。在最坏的情况,冒泡排序需要次交换, 而插入排序只要最多交换。冒泡排序的实现(类似下面)通常会对已经排序好的数列拙劣地执行(),而插入排序在这个例子只需要个运算。 @param arr待排序数组 */ public static void bubbleSort(int [] arr) { for (int i=0; i<arr.length-1;i++) { for (int j=0;j<arr.length-i-1;j++) { if(arr[j+1] > arr[j]) { arr[j+1] = arr[j+1]^arr[j]; arr[j] = arr[j+1]^arr[j]; arr[j+1] = arr[j+1]^arr[j]; } } } } /** 完成插入排序 原理:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 步骤: 从第一个元素开始,该元素可以认为已经被排序 取出下一个元素,在已经排序的元素序列中从后向前扫描 如果该元素(已排序)大于新元素,将该元素移到下一位置 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置后 重复步骤2~5 复杂度分析: 插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中, 需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。 */ public static void insertSort(int arr[]) { for (int i=1;i<arr.length;i++ ) { int key = arr[i]; int position = i; while (position > 0 && arr[position-1]>key) { arr[position] = arr[position-1]; position --; } arr[position] = key; } } /** 完成快速排序 原理:快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。 步骤为: 从数列中挑出一个元素,称为 "基准"(pivot), 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。 在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。 递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去, 但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。 复杂分析:在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较, 但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快, 因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。 */ public static void quickSort(int [] arr,int low, int high) { int pivot; if (low < high) { pivot = getCurrent(arr,low,high); quickSort(arr,low,pivot-1); quickSort(arr,pivot+1,high); } } /** 快排的划分 做法   第一步:(初始化)设置两个指针i和j,它们的初值分别为区间的下界和上界,即i=low,i=high; 选取无序区的第一个记录R[i](即R[low])作为基准记录,并将它保存在变量pivot中;   第二步:令j自high起向左扫描,直到找到第1个关键字小于pivot.key的记录R[j], 将R[j])移至i所指的位置上,这相当于R[j]和基准R[i](即pivot)进行了交换, 使关键字小于基准关键字pivot.key的记录移到了基准的左边,交换后R[j]中相当于是pivot; 然后,令i指针自i+1位置开始向右扫描,直至找到第1个关键字大于pivot.key的记录R[i], 将R[i]移到i所指的位置上,这相当于交换了R[i]和基准R[j],使关键字大于基准关键字的记录移到了基准的右边, 交换后R[i]中又相当于存放了pivot;接着令指针j自位置j-1开始向左扫描,如此交替改变扫描方向, 从两端各自往中间靠拢,直至i=j时,i便是基准pivot最终的位置,将pivot放在此位置上就完成了一次划分。 */ public static int getCurrent(int [] arr, int low, int high) { int pivot = arr[low]; while (low < high ) { while (low<high && arr[high] >= pivot) { high--; } if (low < high) { arr[low++] = arr[high]; } while (low < high && arr[low] <= pivot) { low ++; } if (low < high) { arr[high--] = arr[low]; } } //arr[low] = pivot; arr[high] = pivot; return low; } // 冒泡排序法 public void Sort(int[] list) { long begintime = System.DateTime.Now.Second * 1000 + System.DateTime.Now.Millisecond; Console.WriteLine(begintime); int j, temp; j = 1; while ((j < list.Length)) { for (int i = 0; i < list.Length - j; i++) { if (list[i] < list[i + 1]) { temp = list[i]; list[i] = list[i + 1]; list[i + 1] = temp; } } j++; } long endtime = System.DateTime.Now.Second * 1000 + System.DateTime.Now.Millisecond; Console.WriteLine(endtime); Console.WriteLine(endtime - begintime); } // 选择排序法 public void SortChoice(int[] list) { long begintime = System.DateTime.Now.Millisecond; int min; for (int i = 0; i < list.Length - 1; i++) { min = i; for (int j = i + 1; j < list.Length; j++) { if (list[j] < list[min]) min = j; } int t = list[min]; list[min] = list[i]; list[i] = t; } long endtime = System.DateTime.Now.Millisecond; Console.WriteLine(begintime); Console.WriteLine(endtime); Console.WriteLine(endtime - begintime); } // 插入排序法 public void SortInsert(int[] list) { for (int i = 1; i < list.Length; i++) { int t = list[i]; int j = i; while ((j > 0) && (list[j - 1] < t)) { list[j] = list[j - 1]; --j; } list[j] = t; } } // 希尔排序法 public void SortShell(int[] list) { int inc; for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ; for (; inc > 0; inc /= 3) { for (int i = inc + 1; i <= list.Length; i += inc) { int t = list[i - 1]; int j = i; while ((j > inc) && (list[j - inc - 1] > t)) { list[j - 1] = list[j - inc - 1]; j -= inc; } list[j - 1] = t; } } }

上一篇:[wxWidgets]_[中级]_[移动窗口]
下一篇:iphone开发中数据持久化之——模型对象归档(二)

相关文章

关键词: 排序算法

相关评论