乐趣区

快速排序

疾速排序
思维:任取待排序元素序列中的某个元素作为基准,依照该元素的排序码大小,把整个元素序列分为左右两个子序列:左侧子序列中的所有元素都比基准元素小,右侧所有元素都比基准元素大,而后别离对这两个子序列反复之前的操作,直到整个序列排好序。
例子:
初始序列:基准(pivot)

             21 25 49 25* 16 8            21

1 8 16 21 25 25 49 8(left) 25(right)
2 8 16 21 25* 25 49 25(right)
3 8 16 21 25* 25 49

稳定性:不稳固
工夫复杂度:O(nlogn)
代码:c++
// 疾速排序
void Quick_sort(int arr[],int left,int right) {

   if (left >= right)
          return;
   else {int pivot = arr[left];// 基准
          int i = left;// 左指针
          int j = right;// 右指针
          while (i < j) {// 当左 < 右时,扫描序列
                  while (i < j && arr[j] >= pivot)// 从右往左扫描遇到比基准小的值则停下来
                         j--;
                  while (i < j && arr[i] <= pivot)// 从左往右扫描遇到比基准大的值则停下来
                         i++;
                  if (i<j) {// 而后替换这两个值
                         swap(arr[i], arr[j]);
                  }      
          }
          if (i = j) {// 当扫描到左右指针相遇时,示意扫描完结,将基准值和以后地位的值进行替换

// 咱们始终是以最右边的元素为基准元素的

                  arr[left] = arr[i];
                  arr[i] = pivot;
          }
          Quick_sort(arr, left,i-1);
          Quick_sort(arr, i+1,right);
   }

}

退出移动版