- /*
- * 2013年10月24日19:42:55
- * @yagnchao
- * java 基本语法 ====排序=========
- *---------------------------------------------------------------------------------------------------------
- * 插入排序： 插入排序属于内部排序法，是对于欲排序的的元素以插入的范式找寻该元素的适当位置，已达到排序目的。
- * 插入式排序法（insertion Sorting）的基本思想是： 吧N个待排序的元素堪称为一个有序表和一个无序表，
- * 开始时有序表中只包含一个元素，无序表中包含有N-1个元素，排序过程中每次从无序表中取出第一个元素把它的排序吗一次与
- * 有序表元素的排序码进行比较，将他插入到有序表中的适当位置，使之成为新的有序表。
- * --------------------------------------------------------------------------------------------------------
- *
- * 冒泡排序： 基本思想是：通过对待排序队列从后向前（从下表较大的元素开始），一次比较相邻元素的排序，
- * 就像 水底下的气泡一样逐渐向上冒
- *
- * 优化
- * 因为排序过程中，个元素不断地接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，
- * 因此要在排序过程中设置一个标志flag判断元素是否进行过交换，从而减少不必要的比较。
- * --------------------------------------------------------------------------------------------------------
- *
- * 快速排序法（Quicksort）：是对冒泡排序的一种改进。他的基本思想是：通过一趟排序将要排序的数据分割成为独立的两部分
- * ，qizhognyibufnedesuoyoushuju都比另外一部分的所有数据都要小，然后再按照此方法对这两部分数据分别进行快速排序，
- * 整个排序过程可以递归进行，以此达到整个数据变成有序序列。
- * --------------------------------------------------------------------------------------------------------
- *
- * 选择排序： 选择是排序也属于内部排序发，是从预排序的数据中，按指定的规则选择出某一元素，经过和其他
- * 元素重整，再依原则交换位置后达到排序的目的。
- * --------------------------------------------------------------------------------------------------------
- * */
- package com.test1;
- import java.util.Calendar;
- public class Sort
- {
- public static void main(String[] args)
- {
- int [] m= {1,3,2,5,4,6,9,7,8,12,11,10};
-
- int len = 100000;
- int [] mm = new int[len];
- for(int i=0; i<len; ++i)
- {
- int t = (int)(Math.random()*100000);
- mm[i] = t;
- }
- Bubble bu = new Bubble();
- Select se = new Select();
- Insert in = new Insert();
-
- //测试间
- Calendar cal = Calendar.getInstance();
- System.out.println(cal.getTime());;
- // bu.sort(m);
- // se.sort(mm);
- in.sort(mm);
- cal = Calendar.getInstance();
- System.out.println(cal.getTime());
-
- for (int i=0; i<m.length; ++i)
- {
- System.out.print(m[i] + " ,");
- }
- }
- }
- //冒泡排序法
- class Bubble
- {
- public void sort(int arr[])
- {
- 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;
- }
- }
- }
- }
- }
- //选择排序法
- class Select
- {
- public void sort(int arr[])
- {
- int temp = 0;
-
- for(int i=0; i<arr.length-1; ++i)
- {
- int min = arr[i];//最小数
- int minIndex = i;//记录最小数的下表
-
- for(int j=i+1; j<arr.length; ++j)
- {
- if(min > arr[j])
- {
- min = arr[j];//修改最小数
- minIndex = j;//将最小数的下标
- }
- }
-
- //已经找到最小的数了 然后进行交换
- temp = arr[i];
- arr[i] = arr[minIndex];
- arr[minIndex] = temp;
- }
- }
- }
- //插入式排序法法。
- class Insert
- {
- public void sort(int [] arr)
- {
- 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;
- }
- }
- }
- //交换式排序法---快速排序法
- class QuickSort
- {
- public void sort(int left, int right, int[] arr)
- {
- int l = left;
- int r = right;
- int pivot = arr[(l+r)/2];
- int temp = 0;
-
- while(1<r)
- {
- while(arr[1]<pivot) l++;
- while(arr[r]>pivot) r--;
-
- if(1 >= r) break;
-
- temp = arr[1];
- arr[1] = arr[r];
- arr[r] = temp;
-
- if(arr[1] == pivot) --r;
- if(arr[r] == pivot) ++l;
-
- }
- if (l == r)
- {
- l++;
- r--;
- }
-
- if(left < r) sort(left, r, arr);
- if(right > l) sort(l, right, arr);
- }
- }
|
收藏
淘帖
踩
