Code examples about bubble and quick sort

This article mainly introduces Java Bubble sorting and quick sorting example code. Friends who need it can refer to it

Bubble sorting

Bubble sort is a simple sorting algorithm. It repeatedly walks through the sequence to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The work of visiting the array is repeated until no more exchanges are needed, which means that the array has been sorted. The name of this algorithm comes from the fact that smaller elements will slowly "float" to the top of the array through swapping.

The bubble sorting algorithm is implemented as follows: [After sorting, array is arranged from small to large]

　　/**
  * 冒泡排序
  * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 
  * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 
  * 针对所有的元素重复以上的步骤，除了最后一个。
  * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 
  * @param numbers 需要排序的整型数组
  */
 public static void bubbleSort(int[] numbers)
 {
  int temp = 0;
  int size = numbers.length;
  for(int i = 0 ; i < size-1; i ++)
  {
  for(int j = 0 ;j < size-1-i ; j++)
  {
   if(numbers[j] > numbers[j+1]) //交换两数位置
   {
   temp = numbers[j];
   numbers[j] = numbers[j+1];
   numbers[j+1] = temp;
   }
  }
  }
 }

Quick Sort

The basic idea of ​​quick sort:

The records to be sorted are divided into two independent parts through one sorting pass, where If the keywords of one part of the records are smaller than the keywords of another part, then the two parts will continue to be sorted until the entire sequence is in order.

Treat the entire sequence as an array, regard the zeroth position as the central axis, and compare it with the last one. If it is smaller than it, exchange it, if it is larger than it, no processing will be done; after exchanging it, it will be combined with the smaller one. Compared with that end, if it is smaller than it, don’t exchange it, but if it is larger than it, exchange it. In this way, the cycle goes back and forth, and the sorting is completed in one pass. The left side is smaller than the central axis, and the right side is larger than the central axis. Then the divide and conquer method is used to sort the two independent arrays.

The code is implemented as follows:

1. Find the location of the central axis (the lowest bit is used as the central axis)

　　/**
  * 查找出中轴（默认是最低位low）的在numbers数组排序后所在位置
  * 
  * @param numbers 带查找数组
  * @param low 开始位置
  * @param high 结束位置
  * @return 中轴所在位置
  */
 public static int getMiddle(int[] numbers, int low,int high)
 {
  int temp = numbers[low]; //数组的第一个作为中轴
  while(low < high)
  {
  while(low < high && numbers[high] > temp)
  {
   high--;
  }
  numbers[low] = numbers[high];//比中轴小的记录移到低端
  while(low < high && numbers[low] < temp)
  {
   low++;
  }
  numbers[high] = numbers[low] ; //比中轴大的记录移到高端
  }
  numbers[low] = temp ; //中轴记录到尾
  return low ; // 返回中轴的位置
 }

2, Recursive form of divide and conquer sorting algorithm:

 /**
  * 
  * @param numbers 带排序数组
  * @param low 开始位置
  * @param high 结束位置
  */
 public static void quickSort(int[] numbers,int low,int high)
 {
  if(low < high)
  {
  　　int middle = getMiddle(numbers,low,high); //将numbers数组进行一分为二
  　　quickSort(numbers, low, middle-1); //对低字段表进行递归排序
  　　quickSort(numbers, middle+1, high); //对高字段表进行递归排序
  }
 }

3. Quick sorting provides method call

 /**
  * 快速排序
  * @param numbers 带排序数组
  */
 public static void quick(int[] numbers)
 {
  if(numbers.length > 0) //查看数组是否为空
  {
  quickSort(numbers, 0, numbers.length-1);
  }
 }

Analysis:

Quick sort is generally considered to have the best average performance among sorting methods of the same order of magnitude (O(nlog2n)). However, if the initial sequence is ordered by key or basically ordered, quick sort will degenerate into bubble sort. In order to improve it, the "three-in-one method" is usually used to select the benchmark record, that is, the three record keys centered on the two endpoints and the midpoint of the sorting interval are adjusted as the fulcrum record. Quicksort is an unstable sorting method.

Method Test

PrintFunction:

public static void printArr(int[] numbers)
 {
  for(int i = 0 ; i < numbers.length ; i ++ )
  {
  System.out.print(numbers[i] + ",");
  }
  System.out.println("");
 }

Test:

　public static void main(String[] args) 
 {
  int[] numbers = {10,20,15,0,6,7,2,1,-5,55};
  System.out.print("排序前：");
  printArr(numbers);
  bubbleSort(numbers);
  System.out.print("冒泡排序后：");
  printArr(numbers);
  quick(numbers);
  System.out.print("快速排序后：");
  printArr(numbers);
 }

Result:

Before sorting: 10,20,15,0,6,7,2,1,-5,55 ,

After bubble sort: -5,0,1,2,6,7,10,15,20,55,

After quick sort: -5,0,1, 2,6,7,10,15,20,55,

【Related recommendations】

1. Special recommendation： "php Programmer Toolbox" V0.1 version download

2. Java free video tutorial

3. Comprehensive analysis of Java annotations

The above is the detailed content of Code examples about bubble and quick sort. For more information, please follow other related articles on the PHP Chinese website!