快速排序算法

左手的ㄟ右手 2023-09-29 15:48 2阅读 0赞

步骤:1.先在数组元素中选出一个基准值(pivot)(比较值)

2.将数组中大于基准值(pivot)的元素统一移到基准值右边

将数组中小于基准值(pivot)的元素统一移到基准值左边

3.用递归的方式分别对基准值(pivot)左右两边的子序列重复前两步操作,完成快速排序

基本思路:一般选择将待排序序列分为两个序列,正中间的那个数作为关键字,然后两个指针一个从头到关键字遍历,遇到大于(小于)关键字的元素就停下来,另一个指针从尾到关键字遍历,遇到小于(大于)关键字的元素停下来,交换两个指针的元素完成排序;将序列递归分治按照前面的原理排序,直到序列有序。

平均时间复杂度:O(nlogn)

1.main方法调用排序算法对数组进行排序

  1. public class QuickSort {
  2. private static int count;
  3. public static void main(String[] args) {
  4. int[] arr = {3, 45, 78, 99, 45, 11, 64, 55, 52, 11, 18, 66, 17, 37, 199, 120, 54, 49};
  5. System.out.println("未排序的数组:" + Arrays.toString(arr));
  6. quickSort01(arr, 0, arr.length - 1);
  7. System.out.println("排序的数组:" + Arrays.toString(arr));
  8. }
  1. 快速排序算法(以中间元素为基准)

    /**

    1. * 快速排序算法(以中间元素为基准)
    2. * @param arr 排序的数组
    3. * @param left 左指针
    4. * @param right 右指针
    5. */
    6. private static void quickSort01(int[] arr,int left,int right){
    7. int l = left;
    8. int r = right;
    9. int pivot = arr[(left+right)/2];//选取数组中间元素作为基准
    10. int temp = 0;//temp作为中间转换变量
    11. while (l<r) {
    12. while (arr[l] < pivot) {//当左元素小于基准时,就往右进一位
    13. l++;
    14. }
    15. while (arr[r] > pivot) {//当右元素大于基准时,就往左进一位
    16. r--;
    17. }
    18. if (l >= r) {//当两个指针指向同一个位置时,就跳出循环
    19. break;
    20. }
    21. //交换值,左指针所指大于基准值的与右指针所指小于基准值的交换位置
    22. temp = arr[l];
    23. arr[l] = arr[r];
    24. arr[r] = temp;
    25. if (arr[l] == pivot) {//如果左指针指向元素的值等于基准值,右指针往左移动一格
    26. r--;
    27. }
    28. if (arr[r] == pivot) {//如果右指针指向元素的值等于基准值,左指针往右移动一格
    29. l++;
    30. }
    31. }
    32. //第一次排序结束后,用递归的方式,
    33. //开始对基准值两边的元素开始排序
    34. if (l==r){
    35. l++;
    36. r--;
    37. }
    38. if (left<r){
    39. quickSort01(arr,left,r);
    40. }
    41. if (l<right){
    42. quickSort01(arr,l,right);
    43. }
    44. }

3.快速排序算法(以第一个元素为基准)

  1. /**
  2. * 快速排序算法(以第一个元素为基准)
  3. * @param arr 排序的数组
  4. * @param left 数组的第一个元素索引
  5. * @param right 数组的最后一个元素索引
  6. */
  7. private static void quickSort02(int[] arr,int left,int right){
  8. if (left >= right){
  9. //递归退出条件
  10. return;
  11. }
  12. int l = left;//l为数组的左指针
  13. int r = right;//r为数组的右指针
  14. while (l<r){
  15. while (l<r && arr[r]>=arr[left]) {//如果右指针所指元素大于基准数,就往左移动
  16. r--;
  17. }
  18. while (l<r && arr[l]<=arr[left]){//如果左指针所指元素小于基准数,就往右移动
  19. l++;
  20. }
  21. if (l == r){//如果两个指针指向同一个元素,就将此元素与第一个元素对调位置
  22. int temp = arr[left];
  23. arr[left] = arr[r];
  24. arr[r] = temp;
  25. }else{//如果两个指针没有指向同一个位置,就将两个指针所指向的元素对调位置
  26. int temp = arr[l];
  27. arr[l] = arr[r];
  28. arr[r] = temp;
  29. }
  30. QuickSort.count++;//计算排序总共调用用了多少次
  31. }
  32. quickSort02(arr,left,l-1);//递归方式对基数左边的数进行排序
  33. quickSort02(arr,r+1,right);//递归方式对基数右边的数进行排序
  34. }
  35. }

发表评论

表情:
评论列表 (有 0 条评论,2人围观)

还没有评论,来说两句吧...

相关阅读

    相关 排序算法——快速排序

    排序算法——快速排序 > 快速排序通过一趟排序将待排序序列分隔成独立的两部分,其中一部分序列的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个

    相关 排序算法——快速排序

    前言 快速排序采用了分治法,即将原问题划分成为若干个规模更小且与原问题相似的子问题,然后递归地解决这些子问题,最后将他们组合起来。 快速排序的思想是:假设数据元素存放在

    相关 排序算法-快速排序

    快速排序 是最高效、不占用空间的一种排序算法 快排的精髓 是在于 找到 中间基数。 比中间基数小的放在左边 ,比中间基数大的放在右边 然后 左右各自进行快排。 参考

    相关 排序算法---快速排序

    基本思路: 快速排序,数组冲两边出发。 首先取一个关键字。 在第一次排序后。 大于和小于 关键字的各在 关键字两边。 然后在对两边 重复上面步骤,取关键字,排序。 直