1.排序分类
排序(Sorting)是数据处理中一种很重要的运算，同时也是很常用的运算， 一般数据处理工作25%的时间都在进行排序。 简单地说，排序就是把一组记录(元素)按照 某个域的值的递增(即由小到大)或递减(即由大到小)的次序重新排列的过程。 1、内部排序法：指将需要处理的所有数据都加载到内部存储器中进行排序。 包括(交换式排序法、选择式排序法和插入式排序法)； 2、外部排序法：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。 包括(合并排序法和直接合并排序法)。
2.内部排序法
2.1 交换式排序法
交换式排序属于内部排序法，是运用数据值比较后， 依判断规则对数据位置进行交换，以达到排序的目的。 交换式排序法又可分为两种： 1、冒泡排序法(Bubble Sorting) 2、快速排序法(Quick Sorting)
冒泡排序法案例
冒泡排序(Bubble Sorting)的基本思想是： 通过对待排序序列从后向前(从下标较大的元素开始)，依次比较相邻元素的排序码， 若发现逆序则交换， 使排序码较小的元素逐渐从后部移向前部(从下标较大的单元移向下标较小的单元)， 就象水底下的气泡一样逐渐向上冒。 因为排序的过程中，各元素不断接近自己的位置， 如果一趟比较下来没有进行过交换，就说明序列有序， 因此要在排序过程中设置一个标志flag判断元素是否进行过交换。 从而减少不必要的比较。
//演示冒泡排序法 public class Demo { public static void main(String[] args) { int arr[]={1,6,0,-1,9,-100,90}; int temp=0; //排序 //外层循环，可以决定一共走趟 for(int i=0;i<arr.length-1;i++){ //内层循环，开始逐个比较，如果发现前一个数比后一个数大则交换 for(int j=0;j<arr.length-1-i;j++){ if(arr[j]>arr[j+1]){ //换位 temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } //输出最后结果 for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+"\t"); } } }
2.2 选择式排序法
选择式排序也属于内部排序法，是从欲排序的数据中， 按指定的规则选出某一元素，经过和其他元素重整， 再依原则交换位置后达到排序的目的。 选择式排序又可分为两种： 1、选择排序法(Selection Sorting) 2、堆排序法(Heap Sorting) 选择排序(Select Sorting)也是一种简单的排序方法。 它的基本思想是：第一次从R[0]-R[n-1]中选取最小值，与R[0]交换， 第二次从R[1]-R[n-1]中选取最小值，与R[1]交换， 第三次从R[2]-R[n-1]中选取最小值，与R[2]交换，...， 第i次从R[i-1]-R[n-1]中选取最小值，与R[i-1]交换，...， 第n-1次从R[n-2]-R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次， 得到一个按排序码从小到大排列的有序序列。
选择排序法案例
例如，给定n=8，数组R中的8个元素的排序码为：(8,3,2,1,7,4,6,5)，选择排序过程。 //排序10万个数用时7秒 public class Demo{ public static void main(String []args){ int arr[]={8,3,2,1,7,4,6,5}; int temp=0; for(int j=0;j<arr.length-1;j++){ //认为第一个数就是最小数 int min=arr[j]; //记录最小数的下标 int minIndex=j; for(int k=j+1;k<arr.length;k++){ if(min>arr[k]){ //修改最小值 min=arr[k]; minIndex=k; } } //当退出for循环时就找到这次的最小值 temp=arr[j]; arr[j]=arr[minIndex]; arr[minIndex]=temp; } //输出最后结果 for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+"\t"); } }
2.3 插入式排序法
插入式排序属于内部排序法， 是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。 插入式排序法又可分为3种： 1、插入排序法(Insertion Sorting) 2、谢耳排序法(Shell Sorting)(欧洲人员喜欢使用) 3、二叉树排序法(Binary-tree Sorting)
插入排序案例
插入排序(Insertion Sorting)的基本思想是： 把n个待排序的元素看成为一个有序表和一个无序表， 开始有序表只包含一个元素，无序表中包含有n-1个元素， 排序过程中每次从无序表中取出第一个元素， 把它的排序码依次与有序表元素的排序码进行比较， 将它插入到有序表中的适当位置，使之成为新的有序表。
//插入式排序法，排序10万数据用时2秒 public class Demo{ public static void main(String []args){ int arr[]={23,15,-13,62,5,-23,0,17}; for(int i=1;i<arr.length;i++){ int insertVal=arr[i]; //insertVal准备和前一个数比较 int index=i-1; while(index>=0&&insertVal<arr[index]){ //将把arr[index]向后移动一位 arr[index+1]=arr[index]; //让index向前移动一位 index--; } //将insertVal插入到适当位置 arr[index+1]=insertVal; } //输出最后结果 for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+"\t"); } } }
3.外部排序法
3.1 合并排序法
合并排序法(Merge Sorting)是外部排序最常使用的排序方法。 若数据量太大无法一次完全加载内存， 可使用外部辅助内存来处理排序数据，主要应用在文件排序。 排序方法： 将欲排序的数据分别存在数个文件大小可加载内存的文件中， 再针对各个文件分别使用“内部排序法”将文件中的数据排序好写回文件。 再对所有已排序好的文件两两合并，直到所有文件合并成一个文件后， 则数据排序完成。
//合并排序法 public class Demo{ public static void main(String[] args) { Merge m=new Merge(); int a[]={5,4,10,8,7,9}; m.merge_sort(a,0,a.length-1); } } class Merge{ //递归分成小部分 public void merge_sort(int[] arrays,int start,int end){ if(start<end){ int m=(start+end)/2; merge_sort(arrays,start,m); merge_sort(arrays,m+1,end); combin_arrays(arrays,start,m,end); } } //合并数组 public void combin_arrays(int[] arrays,int start,int m,int end){ int length=end-start+1; int temp[]=new int[length];//用来存放比较的数组，用完复制回到原来的数组 int i=start; int j=m+1; int c=0; while(i<=m &&j<=end){ if(arrays[i]<arrays[j]){ temp[c]=arrays[i]; i++; c++; }else{ temp[c]=arrays[j]; j++; c++; } } while(i<=m){ temp[c]=arrays[i]; i++; } while(j<=end){ temp[c]=arrays[j]; j++; } c=0; for(int t=start;t<=end;t++,c++){ arrays[t]=temp[c]; } snp(arrays); } //打印数组 public void snp(int[] arrays){ for(int i=0;i<arrays.length;i++){ System.out.print(arrays[i]+" "); } System.out.println(); } }
