常见内部排序算法之交换排序

编程技术  /  houtizong 发布于 3年前   67

交换排序，就是不断的交换，一直到适合为止。选择排序主要是不断的选择，然后才交换。
交换排序有两种：
冒泡排序：就像是气泡一样，小的（轻的）一直向上浮动。从最后一个开始一直向前比较，如果比较它小的话就交换。一直滚到最前（相对，如果前面已经循环一次了，则是第二位）。
下面是代码：（下降，大的往后排）

package test.aglorith;import java.util.Arrays;public class BubbleSort {public static void sort(int[] data) {int data_len=data.length;for(int i=0;i<data_len-1;i++){for (int j = 1; j < data_len-i; j++) {if (data[j-1]>data[j]) {int temp=data[j-1];data[j-1]=data[j];data[j]=temp;}}System.out.println(Arrays.toString(data));}}public static void main(String[] args) {int[] data=new int[]{10,9,8,7,6,5,4,3,2,1};System.out.println(Arrays.toString(data));sort(data);}}

快速排序：以第0个数作为中间数，第一个数下标跟最后一个数下标往中间夹，使得左边都比中间数小，右边比中间数大或者相等（恕我表达能力有限）。这样中间数就成为数组分界线了，把数组分成两拨，左边一拨，右边一拨，各自继续排序。以此递归。
代码：（从小到大）

package test.aglorith;import java.util.Arrays;public class QuickSort {public static void sort(int[] data,int low,int hight) {if (hight-low==1) {if (data[hight]<data[low]) {swap(data, low, hight);}}if (hight-low>1) {int left=low+1;int right=hight;int temp=data[low];while (left<=right) {while (left<hight) {if (data[left]<temp) {left++;}else {break;}}while (right>low) {if (data[right]>=temp) {right--;}else {break;}}if (left<right) {swap(data, left, right);left++;right--;}}swap(data, low, right);System.out.println(Arrays.toString(data));sort(data, low, right-1);sort(data, right+1, hight);}}public static void swap(int[] data,int i,int j) {int temp=data[i];data[i]=data[j];data[j]=temp;}public static void main(String[] args) {int[] data=new int[]{5,1,6,4,5,3,2,7};System.out.println(Arrays.toString(data));sort(data,0,data.length-1);System.out.println(Arrays.toString(data));}}