大厂面试常考:快速排序冒泡排序算法

package com.softsec.demo;

/**

  * Created with IDEA

  *

  * @Author Chensj

  * @Date 2020/5/17 19:04

  * @Description

  * @Version 1.0

  */

public class quickSortDemo {

     public static void main(String[] args) {

         // 创建测试数组

         int [] arr = new int []{ 19 , 97 , 9 , 17 , 1 , 8 };

         System.out.println( "排序前：" );

         showArray(arr); // 打印数组

         // 调用快排接口

         quickSort(arr);

         System.out.println( "\n" + "排序后：" );

         showArray(arr); // 打印数组

     }

     /**

      * 快速排序

      * @param array

      */

     public static void quickSort( int [] array) {

         int len;

         if (array == null

                 || (len = array.length) == 0

                 || len == 1 ) {

             return ;

         }

         sort(array, 0 , len - 1 );

     }

     /**

      * 快排核心算法，递归实现

      * @param array

      * @param left

      * @param right

      */

     public static void sort( int [] array, int left, int right) {

         if (left > right) {

             return ;

         }

         // base中存放基准数

         int base = array[left];

         int i = left, j = right;

         while (i != j) {

             // 顺序很重要，先从右边开始往左找，直到找到比base值小的数

             while (array[j] >= base && i < j) {

                 j--;

             }

             // 再从左往右边找，直到找到比base值大的数

             while (array[i] <= base && i < j) {

                 i++;

             }

             // 上面的循环结束表示找到了位置或者(i>=j)了，交换两个数在数组中的位置

             if (i < j) {

                 int tmp = array[i];

                 array[i] = array[j];

                 array[j] = tmp;

             }

         }

         // 将基准数放到中间的位置（基准数归位）

         array[left] = array[i];

         array[i] = base;

         // 递归，继续向基准的左右两边执行和上面同样的操作

         // i的索引处为上面已确定好的基准值的位置，无需再处理

         sort(array, left, i - 1 );

         sort(array, i + 1 , right);

     }

     /**

      * 数组打印

      * @param num

      */

     private static void showArray( int [] num) {

         for ( int i = 0 ; i < num.length; i++) {

             System.out.print(num[i] + " " );

         }

     }

}

#快速排序 传入列表、开始位置和结束位置

def quick_sort( li , start , end ):

     # 如果start和end碰头了，说明要我排的这个子数列就剩下一个数了，就不用排序了

     if not start < end :

         return

     mid = li[start] #拿出第一个数当作基准数mid

     low = start   #low来标记左侧从基准数始找比mid大的数的位置

     high = end  #high来标记右侧end向左找比mid小的数的位置

     # 我们要进行循环，只要low和high没有碰头就一直进行,当low和high相等说明碰头了

     while low < high :

         #从high开始向左，找到第一个比mid小或者等于mid的数，标记位置,（如果high的数比mid大，我们就左移high）

         # 并且我们要确定找到之前，如果low和high碰头了，也不找了

         while low < high and li[high] > mid :

             high - = 1

         #跳出while后，high所在的下标就是找到的右侧比mid小的数

         #把找到的数放到左侧的空位 low 标记了这个空位

         li[low] = li[high]

         # 从low开始向右，找到第一个比mid大的数，标记位置,（如果low的数小于等于mid，我们就右移low）

         # 并且我们要确定找到之前，如果low和high碰头了，也不找了

         while low < high and li[low] < = mid :

             low + = 1

         #跳出while循环后low所在的下标就是左侧比mid大的数所在位置

         # 我们把找到的数放在右侧空位上，high标记了这个空位

         li[high] = li[low]

         #以上我们完成了一次 从右侧找到一个小数移到左侧，从左侧找到一个大数移动到右侧

     #当这个while跳出来之后相当于low和high碰头了，我们把mid所在位置放在这个空位

     li[low] = mid

     #这个时候mid左侧看的数都比mid小，mid右侧的数都比mid大

     #然后我们对mid左侧所有数进行上述的排序

     quick_sort( li , start, low - 1 )

     #我们mid右侧所有数进行上述排序

     quick_sort( li , low + 1 , end )

#入口函数

if __name__ = = '__main__' :

     li = [ 19 , 97 , 9 , 17 , 1 , 8 ]

     quick_sort(li , 0 , len (li) - 1 )

     print (li)