버블 정렬과 버블 정렬의 두 가지 최적화

버블 정렬 알고리즘의 작동은 다음과 같습니다. 두 개의 인접한 요소를 앞에서 뒤로 비교합니다. 두 번째 요소가 첫 번째 요소보다 작으면 마지막 요소와 같아질 때까지 두 요소를 교환합니다. 가장 큰 요소가 마지막에 배치되도록 비교를 (n-1) 번 반복하면 정렬이 완료됩니다.

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

Quicksort 알고리즘(버블 정렬의 최적화):

1) 정렬이 시작될 때 두 변수 i와 j를 설정합니다. =0, j=N-1;

2) 첫 번째 배열 요소를 키 데이터로 사용하고 이를 키에 할당합니다. 즉, key=A[0]; j부터 정방향 검색을 시작합니다. 즉, 뒤에서 정방향으로 검색(j--)하고, 키보다 작은 첫 번째 값 A[j]를 찾아 A[j]와 A[i]를 교환합니다.

4) i부터 역방향 검색, 즉 앞에서 뒤로 검색(i++)하여 키보다 큰 첫 번째 A[i]를 찾아 A[i]와 A[j]를 교환합니다.

5) i=j가 될 때까지 3단계와 4단계를 반복합니다. (3단계와 4단계에서는 조건을 충족하는 값이 발견되지 않습니다. 즉, 3의 A[j]는 키보다 작지 않고 A[i]는 4는 키보다 크지 않습니다. j=j-1, i=i+1이 되도록 j와 i의 값을 변경할 때 조건에 맞는 값을 찾을 때까지 i와 j 포인터 위치는 동안 변경되지 않고 유지됩니다. 이 프로세스는 i+ 또는 j-가 완료될 때 발생해야 하며 이 시점에서 루프가 종료됩니다.

                                                                                플래그(부호)를 설정합니다(버블 정렬의 또 다른 최적화 방법). 각 비교가 완료된 후 요소가 교환되었는지 확인하십시오. 그렇다면 다음 주기를 계속하십시오. 그렇지 않으면 루프를 종료합니다.

이 "플래그 비트 설정" 방법은 "빠른 정렬 알고리즘"만큼 효율적이지 않습니다.

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

C 언어 코드는

때 n이 크면 시간 복잡도를 사용해야 합니다. O(nlog2n) 정도의 정렬 방법: 빠른 정렬, 힙 정렬 또는 병합 정렬.

/*
** 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);
}

퀵 정렬: 현재 비교 기반 정렬 중 가장 좋은 방법으로 간주됩니다. 정렬할 키워드가 무작위로 분포되어 있으면 퀵 정렬의 평균 시간이 가장 짧습니다. 🎜>

버블 정렬과 버블 정렬의 두 가지 최적화에 대한 더 많은 기사를 보려면 PHP 중국어 웹사이트를 주목하세요!