冒泡排序
对于一个数组来说，每次相邻两个元素进行比较，如果第二个元素小于第一个元素就进行交换（升序排序的情况），这样子每次循环完毕后，待排序数组里面最大的值都会移动到末尾，下次循环就可以不用考虑判断末尾的情况了。
时间复杂度：O（n方）
public void bubbleSort(int[] q) {
for(int i = 1; i < q.length; i++) {
for(int j = 0; j < q.length - i; j++) {
if(q[j] > q[j + 1]) {
int temp = q[j];
q[j] = q[j + 1];
q[j + 1] = temp;
}
}
}
}
选择排序
在第i次循环中，每次从待排序的数组中选择一个最小的元素，放到第i个位置。那么循环结束后就可以得到一个升序数组了
时间复杂度：O（n方）
public static void selectSort(int[] q) {
for(int i = 0; i < q.length - 1; i++) {
int min = i;
for(int j = i + 1; j < q.length; j++) {
if(q[j] < q[min]) {
min = j;
}
}
if(i != min) {
int temp = q[i];
q[i] = q[min];
q[min] = temp;
}
}
}
插入排序
每次循环，前i个位置构成的数组都是有序的数组，即每次都会把新的元素与他之前的元素进行比较，如果新元素小就互换位置，while循环会一直换直到新元素到了该到的位置，这样子新的数组又是一个有序数组，然后在去把下一个元素插入进来。虽然名字是插入排序，但是因为每次都要与前面一个进行比较再互换，所以还是稳定的排序。
时间复杂度：O（n方）
public void insertSort(int[] q) {
for(int i = 1; i < q.length; i++) {
int j = i;
while(q[j] < q[j - 1] && j > 0) {
int temp = q[j];
q[j] = q[j - 1];
q[j - 1] = temp;
j --;
}
}
}
归并排序
分治法是把一个问题分成n个子问题去看待。要对一个数组排序，可以把它分成两个同等规模的数组，这两个数组分别排序完后再合并成一个有序数组，而两个数组可以分为四个同等规模的数组，一直分到最后一个数组只有两个元素。合并的过程就是申请一个新数组，然后双指针，哪个数组指向的小就放到新数组中，最后有个数组会有剩下来的值，直接放到新数组的末尾。
public void merge(int []q, int l, int r) {
if(l >= r) return;
int mid = ((r - l) >> 1) + l;
merge(q, l, mid);
merge(q, mid + 1, r);
int k = 0;
int i = l;
int j = mid + 1;
int []temp = new int[q.length];
while(i <= mid && j <= r) {
if(q[i] <= q[j]) {
temp[k ++ ] = q[i ++ ];
}else {
temp[k ++ ] = q[j ++ ];
}
}
while(i <= mid) temp[k ++ ] = q[i ++ ];
while(j <= r) temp[k ++ ] = q[j ++ ];
for(i = l, j = 0; i <= r; i++, j++) {
q[i] = temp[j];
}
}
快速排序
选择一个最中间的元素当做基准，然后双指针指向头和尾，如果头指针的元素小于中间值就继续往后移动，如果尾指针的元素大于中间值就往前移动，当他们两个都停下来的时候，如果头指针小于尾指针的位置，那么就交换两个位置的元素，然后一直循环直到头指针大于等于尾指针的位置。一次快排就结束了，这个时候j这个位置左边的元素都比他小，右边的元素都比他大，分别进行两次快排。
时间复杂度：O（nlogn），正常情况下快排的速度比归并还快，但是快排也是一种不稳定的排序，不稳定的排序一般有四种，快希选堆（快速排序，希尔排序，选择排序，堆排序）
public void quickSort(int[] q, int l, int r) {
if(l >= r)
return;
int i = l - 1;
int j = r + 1;
int x = q[l + r >> 1];
while(i < j) {
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if(i < j) {
int temp = q[i];
q[i] = q[j];
q[j] = temp;
}
}
quickSort(q, l, j);
quickSort(q, j + 1, r);
}
