冒泡排序:
冒泡排序:不断遍历文件,交换倒序的相邻元素,直到文件排好顺序。
冒泡排序的主要优点是容易实现,冒泡排序通常会比其他排序慢。复制代码 快速排序:
快速排序是对冒泡排序的一种改进。原理可以参照http://blog.csdn.net/sws9999/article/details/2791812- public class QuickSort {
- public int[] array = {8,2,4,7,0,1};
- protected void display(int [] a){
- for(int i : a)
- System.out.print(i + "\t");
- }
- protected void swap(int [] a , int bigger , int smaller){
- int temp;
- temp = a[bigger];
- a[bigger] = a[smaller];
- a[smaller] = temp;
- }
- <FONT color=yellowgreen>/**
- *
- * 对三点进行排序
- *
- * @param a
- * @param first
- * @param mid
- * @param last
- */</FONT>
- private void sortPivots(int [] a , int first , int mid , int last){
- sortForTwo(a, first, mid);
- sortForTwo(a , mid , last);
- sortForTwo(a, first, mid);
- }
- private void sortForTwo(int [] a , int before , int after){
- if(a[before] > a[after]){
- swap(a, before, after);
- }
- }
- private int partition(int [] a, int first , int last){
- <FONT color=yellowgreen>//设置支点</FONT>
- int mid = (first + last)/2;
- sortPivots(a, first, mid, last);
- <FONT color=yellowgreen> //将支点移动到数组中的倒数第二个位置</FONT>
- swap(a, mid, last - 1);
- int pivotIndex = last - 1;
- int pivot = a[pivotIndex];
- <FONT color=yellowgreen>//确定子数组
- </FONT> int indexFromLeft = first + 1;
- int indexFromRight = last - 2;
- boolean done = false;
- while(!done){
- <FONT color=yellowgreen>//从数组的左边开始,留下小于支点的元素</FONT>
- while(a[indexFromLeft] < pivot)
- indexFromLeft++;
- <FONT color=yellowgreen>//从数组的右边开始,留下大于支点的元素
- </FONT> while(a[indexFromRight] > pivot)
- indexFromRight--;
- <FONT color=yellowgreen>//交换数据
- </FONT> if(indexFromLeft < indexFromRight){
- swap(a, indexFromLeft, indexFromRight);
- indexFromLeft ++;
- indexFromRight--;
- }else
- done = true;
- }
- <FONT color=yellowgreen> //将支点放在较小部分和较大部分字数组之间
- </FONT> swap(a, pivotIndex, indexFromLeft);
- pivotIndex = indexFromLeft;
- return pivotIndex;
- }
- private int [] sort(int [] a , int first , int last){
- if(last - first + 1 < 4){
- <FONT color=yellowgreen>//选择别的排序
- </FONT> for(int i = 0 ; i < a.length ; i ++){
- for(int j = i + 1 ; j < a.length ; j ++){
- if(a[i] > a[j])
- swap(a , i , j);
- }
- }
- }else{
- <FONT color=yellowgreen>//创建划分
- </FONT> int pivotIndex = partition(array, first, last);
- <FONT color=yellowgreen>//对较小部分和较大部分分别进行快速排序
- </FONT> sort(a, first, pivotIndex - 1);
- sort(a, pivotIndex + 1 , last);
- }
- return array;
- }
- public static void main(String[] args) {
- QuickSort q = new QuickSort();
- q.array = q.sort(q.array, 0 , q.array.length - 1);
- q.display(q.array);
- }
- }
复制代码 |