Bubble sort and two optimizations of bubble sort

The bubble sort algorithm works as follows: compare two adjacent elements one at a time from front to back. If the second element is smaller than the first element, swap the two elements until it is compared with the last element. Complete, so that the largest element is placed at the end; in this way, the sorting can be completed by repeating the comparison (n-1) times.

------------------------------------------------ -------------------------------------------------- ----

          Quicksort algorithm (an optimization of bubble sort):

1) Set two variables i, j, when sorting starts: i=0, j=N-1;

2) Use the first array element as the key data and assign it to key, that is, key=A[0];

3) Search forward starting from j, that is, search forward from the back (j--), and find The first value A[j] that is smaller than key, interchange A[j] and A[i];

4) Search backward from i, that is, search backward from the front (i++), find the first A[i] that is larger than key, exchange A[i] and A[j];

5) Repeat steps 3 and 4 until i=j; (In steps 3 and 4, no qualified match was found value, that is, when A[j] in 3 is not less than key, and when A[i] in 4 is not greater than key, change the values ​​of j and i so that j=j-1, i=i+1, until a match is found. When the value of the condition is exchanged, the positions of the i and j pointers remain unchanged. In addition, the process of i==j must be exactly when i+ or j- is completed, and the loop ends at this time).

                                                                                           Set the flag (sign) (another optimization method of bubble sort). After each comparison is completed, see whether the elements are exchanged. If so, continue the next cycle. If not, end the cycle.

This method of "setting the flag bit" is not as efficient as the "quick sort algorithm".

------------------------------------------------ -------------------------------------------------- ----

The C language code is as follows:

/*
** bubble sort
*/ 
void bubble_sort(int *str, int size)
{
     int i = 0, j = 0;
     int tmp = 0;
      
     /*
     ** 进行size-1趟排序；
     */
     for (i = 0; i < size - 1; i++)
     {
         /*
         ** 每排序一趟，将最大的元素沉底。下一趟少比较i次；
         */
 
          for (j = 0; j < size - 1 - i; j++)       
          {
               if (str[j] > str[j + 1])
               {
                    tmp = str[j];
                    str[j] = str[j + 1];
                    str[j + 1] = tmp;
               }
          }
 
     }
}
 
/*
** 优化一：设置一个标志位sign的bubble sort；
*/
 void bubble_sort(int *str, int size)
{
     int i = 0, j = 0;
     int tmp = 0, sign = 0;
      
     for (i = 0; i < size - 1; i++)
     {
          /*
          ** 每趟排序前将sign置为0，如果相邻元素进行了交换则sign>1;
          ** 否则，sign==0，没有进行交换，排序完成，跳出循环；
          */
          flag = 0;
          for (j = 0; j < size - 1 - i; j++)
          {
               if (str[j] > str[j + 1])
               {
                    tmp = str[j];
                    str[j] = str[j + 1];
                    str[j + 1] = tmp;
                    sign++;
               }
          }
          if (0 == sign)
          break;
     }
}
 
 
/*
** 优化二：quick sort；
*/
void quicksort(int *str, int left, int right)
{
     assert(str);
      
     /*
     **如果左边大于或等于右边，则该数组已经排序完成；
     */
     if (left >= right)
     {
          return;
     }
      
     int i = left;
     int j = right;
     int key = str[left];
      
     /*
     **当i=j时，一趟排序完成，将所有数分为一大一小两组；
     */
     while (i < j)
     {
          /*
          **第一次从后向前遍历，遇到第一个比key小的交换两数位置；
          */
          while ((i < j) && (key <= str[j]))
          {
               j--;
          }
          str[i] = str[j];
           
          /*
          **第二次从前向后遍历，遇到第一个比key大的交换两数位置；
          */
          while ((i < j) && (key >= str[i]))
          {
               i++;
          }
          str[j] = str[i];
     }
      
     str[i] = key;
     /*
     **递归调用，完成左、右子序列的排序；
     */
     quicksort(str, left, i - 1);
     quicksort(str, i + 1, right);
}

When n is large, a sorting method with a time complexity of O(nlog2n) should be used: quick sort, heap sort or merge sort.

Quick sort: It is currently considered the best method among comparison-based internal sorting. When the keywords to be sorted are randomly distributed, the average time of quick sort is the shortest;

More risks For related articles on bubble sorting and two optimizations of bubble sorting, please pay attention to the PHP Chinese website!