快速排序:快速排序(Quicksort)是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
在这里我给大家提供个网站 http://www.atool.org/sort.php,是关于各种排序算法演示过程的。好了,不多赘述,直接上代码。
方法一
1 package com.feimao.com.feimao.a2.test; 2 3 import java.util.Arrays; 4 5 public class QuickSort { 6 public static void quickSort(int arr[], int start, int end) { 7 if (start < end) { 8 int stard = arr[start];//把数组中的第0个数字作为基准 9 int low = start; 10 int high = end;//记录排序下标 11 while (low < high) {//循环找出比标准数大的数字比标准数小的数 12 while (low < high && stard <= arr[high]) {//右边的数比标准数大 13 high--; 14 } 15 arr[low] = arr[high];//使右边的数字替换左边的数字 16 while (low < high && arr[low] <= stard) {//如果左边的数字比标准数小 17 low++; 18 } 19 arr[high] = arr[low]; 20 } 21 arr[low] = stard;//把标准数赋值给低所在的元素 22 quickSort(arr, start, high - 1);//处理所有小的数字 23 quickSort(arr, high + 1, end);//处理所有大的数字 24 25 } 26 } 27 28 public static void main(String[] args) { 29 int arr[] = {3, 4, 6, 7, 2, 7, 2, 8, 0}; 30 quickSort(arr, 0, arr.length - 1); 31 System.out.println(Arrays.toString(arr)); 32 33 } 34 }
方法二
1 public class QuickSort { 2 public static void quickSort(int[] arr,int low,int high){ 3 int i,j,temp,t; 4 if(low>high){ 5 return; 6 } 7 i=low; 8 j=high; 9 //temp就是基准位 10 temp = arr[low]; 11 12 while (i<j) { 13 //先看右边,依次往左递减 14 while (temp<=arr[j]&&i<j) { 15 j--; 16 } 17 //再看左边,依次往右递增 18 while (temp>=arr[i]&&i<j) { 19 i++; 20 } 21 //如果满足条件则交换 22 if (i<j) { 23 t = arr[j]; 24 arr[j] = arr[i]; 25 arr[i] = t; 26 } 27 28 } 29 //最后将基准为与i和j相等位置的数字交换 30 arr[low] = arr[i]; 31 arr[i] = temp; 32 //递归调用左半数组 33 quickSort(arr, low, j-1); 34 //递归调用右半数组 35 quickSort(arr, j+1, high); 36 } 37 38 39 public static void main(String[] args){ 40 int[] arr = {3 , 4 , 6 , 7 , 2 , 7 , 2 , 8 , 0}; 41 quickSort(arr, 0, arr.length-1); 42 for (int i = 0; i < arr.length; i++) { 43 System.out.println(arr[i]); 44 } 45 } 46 }