排序算法之 ____ 快速排序

快速排序是对冒泡排序的一种改进.

快速排序算法的基本思想是: 将所要进行排序的数分为左右两个部分, 其中一部分的所要数据都比另外一部分的数据小, 然后将所分得的两部分数据进行同样的划分, 重复执行以上划分操作, 知道所有要进行排序的数据变为有序数据为止.

代_码

#include <stdio.h>
void patiton(int arr[], int low, int high) { //分别定义low和high为要进行排序的其实元素  和最后一个元素的下标, 第一次low和high的取值分别为0何n-1
     int key;  //定义key作为基准将数组分为左右两个部分
     key = arr[low];
     while(low < high) {
          while(low<high && arr[high] >= key)
          high--;
      if(low < high)
         arr[low++] = arr[high];
      while(low < high && arr[low] <= key)
           low++;
      if(low < high)
         arr[high--] = arr[low];
     }
     arr[low] = key;
     return low;
}
void quick_sort(int arr[], int start, int end) {
     int pos;
     if(start < end) {
        pos = partition(arr, start, end);
        quick_sort(arr, start,pos-1);
        quick_sort(arr,pos+1,end);
     }
     return;
}
int main () {
    int arr[] = {32, 12, 8, 76, 21, 17, 24, 49, 78, 3};
    quick_sort(arr, 0, 9);
    for(int i= 0; i < 10; i++) 
     printf("%d  ", arr[i]);
}

运行结果:

性能

快速排序的时间复杂度为O(NlogN, 空间复杂度为O(logN), 但最坏情况下, 时间复杂度为O(N^2), 空间复杂度为O(N); 且排序是不稳定的, 但每次都能确定一个元素所在序列中的最终位置, 复杂度和初始序列有关.

         ==~ end ~==