【入门】面试408机试-排序（冒泡排序、快排）
目标软件测试日常实习岗，搜了搜面经，机试题不会太难，但也不太简单，故记录一下。
一、冒泡排序
做为面试中常见的简单题，需要能够手撕，冒泡排序的时间复杂度为O（n^2）
1.1题目描述
将读入的 NN 个数从小到大排序后输出。
输入格式
第一行为一个正整数 NN。
第二行包含 NN 个空格隔开的正整数 a_iai，为你需要进行排序的数。
输出格式
将给定的 NN 个数从小到大输出，数之间空格隔开，行末换行且无空格
输入 ： 5 4 2 4 5 1 输出 1 2 4 4 5
1.2C++代码实现
#include<bits/stdc++.h>
using namespace std;
int a[10010];
int main(){int n,t;cin>>n;for(int i=0;i<n;i++){cin>>a[i];}for(int i=0;i<n-1;i++){for(int j=1;j<n;j++){if(a[j]<a[j-1]){t=a[j-1];a[j-1]=a[j];a[j]=t; }}}for(int i=0;i<n;i++){cout<<a[i]<<" ";}}稍微改进了一点点，j<n 改成了 j<n-i，这样复杂度就可以小一点点
#include<bits/stdc++.h>
using namespace std;
int a[10010];
int main(){int n,t;cin>>n;for(int i=0;i<n;i++){cin>>a[i];}for(int i=0;i<n-1;i++){for(int j=1;j<n-i;j++){if(a[j]<a[j-1]){t=a[j-1];a[j-1]=a[j];a[j]=t; }}}for(int i=0;i<n;i++){cout<<a[i]<<" ";}}1.3python实现
虽然c++和java语法是平常练习常用的格式，但测试岗更倾向用python考察代码功底，所以必须要会用python写。（平常都是做深度学习代码，基本上就是该模块调参，python写算法题还真不太熟练……）
# 输入数组的长度 n
n = int(input())# 初始化一个长度为 n 的列表
array = [0] * n# 循环输入 n 个元素，并存储到数组的对应位置
for i in range(n):array[i] = input()for i in range(n):for j in range(n-1):if(array[j]>array[j+1]):t=array[j]array[j]=array[j+1]array[j+1]=t# 输出最终的数组
print(array)
把array弄成固定长度数组……算是活生生创造了一个缺点，不过可以当个小模版。
# 输入数组的长度 n
n = int(input())
# 初始化一个长度为 n 的列表
array = [0] * n
# 循环输入 n 个元素，并存储到数组的对应位置
for i in range(n):array[i] = input()
……
# 输出最终的数组
print(array)
看了看测开实习的面试题，python手撕难度好像就这么高？难得算法题好像也没说要用python写了。
二、快速排序
难度比冒泡高不少。时间复杂度O（nlogn）
以前做c++算法题的时候经常用sort，没想到有的公司要手撕……
算法思路
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
多次比较，多次交换，这好像二分啊
可以参考这篇博客：排序——快速排序（Quick sort）-CSDN博客
首先用数组的第一个数（最后一个也行）作为枢轴，然后将所有比它小的数都放到它的位置之前，所有比它大的数都放到它的位置之后，由此可以该“枢轴“记录最后所落的位置 i 作为分界线，将序列分割成两个子序列。之后再递归这个过程。
大佬的代码看了半天，还是不太懂……只能尝试背过了囧
#include <iostream>
using namespace std;
void QuickSort(int *array,int low,int high){ //快排 if(low>=high){ //若待排序序列只有一个元素，返回空 return ;}int i=low; //i作为指针从左向右扫描 int j=high; //j作为指针从右向左扫描int key=array[low];//第一个数作为基准数 while(i<j){while(array[j]>=key&&i<j){ //从右边找小于基准数的元素 （此处由于j值可能会变，所以仍需判断i是否小于j） j--; //找不到则j减一 }array[i]=array[j]; //找到则赋值 while(array[i]<=key&&i<j){ //从左边找大于基准数的元素 i++; //找不到则i加一 }array[j]=array[i]; //找到则赋值 }array[i]=key; //当i和j相遇，将基准元素赋值到指针i处 QuickSort(array,low,i-1); //i左边的序列继续递归调用快排 QuickSort(array,i+1,high); //i右边的序列继续递归调用快排
}int main(){int array[1000];int n;cin>>n;for(int i=0;i<n;i++){cin>>array[i];}cout<<endl;QuickSort(array,0,n-1);cout<<"快排序列(递增)：";for(int i=0;i<n;i++){cout<<array[i]<<" ";}return 0;
}中间的两个array和key的比较，改一下大于等于和小于等于号，就是递减排序了。
while(i<j){while(array[j]<=key&&i<j){ //从右边找小于基准数的元素 （此处由于j值可能会变，所以仍需判断i是否小于j） j--; //找不到则j减一 }array[i]=array[j]; //找到则赋值 while(array[i]>=key&&i<j){ //从左边找大于基准数的元素 i++; //找不到则i加一 }array[j]=array[i]; //找到则赋值 }