快速排序属于交换排序。
算法思想：
快速排序的核心思想是分治法，通过选择一个基准元素(pivot)，将序列分为两部分：小于基准的部分和大于基准的部分。然后递归地对这两部分进行排序。
在数组或者顺序存储的序列中，可以通过随机访问快速找到任意位置的元素，并通过交换操作高效地完成分区（partition）。然而，链表是顺序访问的数据结构，无法像数组一样高效地支持随机访问和交换操作。
在待排序表[1...n]中任取一个元素pivot作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分为独立的两部分L[1...k-1]和L[k+1...n]，使得L[1...k-1]中的所有元素小于pivot，L[k+1...n]中的所有元素大于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。
//分区函数，返回枢轴元素的最终位置
int partition(int A[],int left,int right){if(left>=right) return left;//先设置随机数种子，确保每次运行程序时生成不同的随机数序列srand(time(NULL));//在当前序列中随机选一个元素作为枢轴int random_pos = left + rand()%(right - left +1);//将随机选择的枢轴元素交换到数组的第一个位置int temp = A[random_pos];A[random_pos] = A[left];A[left] = temp;int pivot = A[left];//用新的第一个元素作为枢轴while(left<right){ //用left和right搜索枢轴元素的最终位置//从右向左找到第一个小于等于枢轴的元素while(left<right && A[right]>pivot) right--;A[left] = A[right];//从左向右找到第一个大于枢轴的元素while(left<right && A[left]<=pivot) left++;A[right] = A[left];}A[left] = pivot;//把枢轴元素存放到最终位置return left; //返回存放枢轴元素的最终位置
}void quick_sort(int A[],int left,int right){if(left>=right) return;//递归结束int pivot_position = partition(A,left,right);quick_sort(A,left,pivot_position-1);quick_sort(A,pivot_position+1,right);
}总结
算法表现主要取决于递归深度，若每次“划分”越均匀，则递归深度越低。“划分”越不均匀，递归深度越深。
| 最好时间复杂度 | O(nlogn)，每次划分很平均 |
| 最坏时间复杂度 | O(n^2)，原本正序或逆序 |
| 平均时间复杂度 | O(nlogn) |
| 最好空间复杂度 | O(logn)每次划分很平均 |
| 最坏空间复杂度 | O(n) |
| 稳定性 | 不稳定 |
| 适用性 | 仅适用于顺序表，不适用于链表 |
