冒泡排序:
冒泡排序:不断遍历文件,交换倒序的相邻元素,直到文件排好顺序。
冒泡排序的主要优点是容易实现,冒泡排序通常会比其他排序慢。
- public class Bubble {
- public int[] array = {8,2,4,7,0,1};
- private void sort(){
- <FONT color=yellowgreen>/*
- 当i=0时进入第一轮外层循环将第一个元素8依次与后面五个元素比较,若比后面元素大则交换位置,经过第一轮循环后,将最小的元素0换在第一个位置。
- {8,2,4,7,0,1}==》{2,8,4,7,0,1}==》{0,8,4,7,2,1}
- 当i=1时进入第二轮循环将第二个元素8依次与后面四个元素比较,若比后面元素大则交换位置,经过第一轮循环后,将次小的元素1换在第二个位置。
- {0,8,4,7,2,1}==》{0,4,8,7,2,1}==》{0,2,8,7,4,1}==>{0,1,8,7,4,2}
- 当i=2时进入第三轮循环将第三个元素8依次与后面三个元素比较,若比后面元素大则交换位置,经过第一轮循环后,将第三小的元素2换在第三个位置。
- {0,1,8,7,4,2}==》{0,1,7,8,4,2}==》{0,1,4,8,7,2}==>{0,1,2,8,7,4}
- 当i=3时进入第四轮循环将第四个元素8依次与后面两个元素比较,若比后面元素大则交换位置,经过第一轮循环后,将第四小的元素4换在第四个位置。
- {0,1,2,8,7,4}==》{0,1,2,7,8,4}==》{0,1,2,4,8,7}
- 当i=4时进入第五轮循环将第五个元素8依次与最后一个元素比较,若比后面元素大则交换位置,经过第一轮循环后,将第五小的元素7换在第五个位置。
- {0,1,2,4,8,7}==》{0,1,2,4,7,8}
- 当i=5时候,不满足i<array.length-1,退出外层循环比较结束。
- */</FONT>
- for(int i = 0 ; i < array.length-1 ; i ++){
- <FONT color=yellowgreen> /*当i=0时,内层循环数据交换情况
- 当j=1时,a[i]=a[0]=8,a[j]=a[1]=2,此时a[0]>a[j]需要交换位置,数组的次序变为{2,8,4,7,0,1},j自增一次变为2
- 当j=2时,a[i]=a[0]=2,a[j]=a[2]=4,此时a[0]<a[j]保持原顺序,数组的次序仍为{2,8,4,7,0,1},j自增一次变为3
- 当j=3时,a[i]=a[0]=2,a[j]=a[3]=7,此时a[0]<a[j]保持原顺序,数组的次序仍为{2,8,4,7,0,1},j自增一次变为4
- 当j=4时,a[i]=a[0]=2,a[j]=a[4]=0,此时a[0]>a[j]需要交换位置,数组的次序仍为{0,8,4,7,2,1},j自增一次变为5
- 当j=3时,a[i]=a[0]=0,a[j]=a[5]=1,此时a[0]<a[j]保持原顺序,数组的次序仍为{0,8,4,7,2,1},j自增一次变为6
- 当j=6=array.length时候不满足内层循环条件跳出内层循环,i自增一次变为1,进入外层循环,内层循环共执行array.lenght-1次
- */</FONT>
- for(int j = i + 1 ; j < array.length ; j ++){
- if(array[i] > array[j])
- swap(array , i , j);
- }
- }
- display(array);
- }
- private void display(int [] a){
- for(int i : a)
- System.out.print(i + "\t");
- }
- private void swap(int [] a , int bigger , int smaller){
- int temp;
- temp = a[bigger];
- a[bigger] = a[smaller];
- a[smaller] = temp;
- }
- public static void main(String[] args) {
- Bubble b = new Bubble();
- b.sort();
- }
- }
复制代码 快速排序:
快速排序是对冒泡排序的一种改进。原理可以参照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);
- }
- }
复制代码 |