Java实现快速排序算法-Quick Sort

    科技2022-07-20  120


    算法简介

    快速排序(Quick Sort) 是由冒泡排序改进而得的。在冒泡排序过程中,只对相邻的两个记录进行比较,因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个(不相邻)记录的一次交换直接消除多个逆序,则会大大加快排序的虚度。快速排序方法中的一次交换可以消除多个逆序。

    算法步骤

    在待排序的n个记录中任取一个记录(通常选取第一个记录)作为枢轴,设其关键字为pivotkey。经过一趟排序后,把所有关键字小于pivotkey的记录交换的前面,把所有大于pivotkey的记录交换到后面,结果将待排序记录分成两个子表,最后将枢轴放置在分界处的位置。然后对左右两个子表重复上述过程,直到每一个子表只有一个记录时,排序完成。换句话说,就是每一趟排序都将一条记录放在了正确的位置上。(正确位置就是完成排序时它所处的位置)

    具体步骤

    选择待排序表中第一个记录作为枢轴,保存在变量pivotkey中。附设两个指针low和high,初始时分别指向表的上界和下界(第一趟时,low = 0;high = nums.length)。从表的最右侧位置依次向左侧搜索,当找到第一个值小于pivotkey的记录时,将其移动到low处。具体操作是:当low < high时,若high所指记录大于等于pivotkey,则向左移动指针high;否则移动该记录。然后从表的最左侧位置依次向右侧搜索,找到第一个关键字大于pivotkey的记录,将其移动到high处。具体操作是:若low所指记录的值小于pivotkey,则向右移动指针low;否则移动该记录。重复步骤2和3,直至low和high。此时low和high的位置即为枢轴在此躺排序的最终位置,原表被分为两个子表。

    代码实现

    public class Sort { public static void main(String[] args) { int[] nums = new int[]{1, 321, 34, 54, 56, 745, 7546,3,423,463,64,234,143421}; quickSort(nums); for (int n : nums) { System.out.println(n); } // 1 // 3 // 34 // 54 // 56 // 64 // 234 // 321 // 423 // 463 // 745 // 7546 // 143421 } public static void quickSort(int[] nums) { qSort(nums,0,nums.length - 1); } public static void qSort(int[] nums,int low,int high) { if(low < high) { int pivotloc = partition(nums,low,high); qSort(nums,low,pivotloc - 1); qSort(nums,pivotloc+1,high); } } public static int partition(int[] nums,int low,int high) { int pivotkey = nums[low]; //用于比较的枢轴 while (low < high) { while (low < high && nums[high] >= pivotkey) { high --; } nums[low] = nums[high]; while (low < high && nums[low] <= pivotkey) { low ++;} nums[high] = nums[low]; } nums[low] = pivotkey; return low; } }
    Processed: 0.010, SQL: 8