开始重新找工作了，复习一下常用算法和数据结构
冒泡排序
/**
* 冒泡排序
* 每趟冒出一个最大数/最小数
* 每次运行数量：总数量-运行的趟数(已冒出)
*/
public void bubbleSort() {
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int t = array[j];
array[j] = array[j + 1];
array[j + 1] = t;
}
}
}
}
选择排序
/***
* 选择排序
* 每趟选择一个最大数/最小数
* 每次运行数量：总数量-运行的趟数(已选出)
*/
public void selectSort(){
for(int i = 0; i < elems-1; i++) {//排序趟数 n-1次就行了
int min = i;
for(int j = i+1; j < elems; j++){ //排序次数 每趟选择一个数出来，-1次
if(intArray[j] < intArray[min]){
min = j;
}
}
if(i != min ){
int temp = intArray[i];
intArray[i] = intArray[min];
intArray[min] = temp;
}
display();
}
}
插入排序
/**
* 插入排序
* 每趟选择一个待插入的数
* 每次运行把待插入的数放在比它大/小后面
*/
public void insertSort(int[] array) {
for (int i = 0; i < array.length; i++) {
int temp = array[i];
int j = i;
while (j > 0 && temp < array[j - 1]) {
array[j] = array[j - 1];
j--;
}
array[j] = temp;
}
}
快速排序
/**
* 快速排序
* 选择一个基准数将数组利用递归二分，直到数组不能再分为止；
*/
public void quickSort(int[] array, int low, int high) {// 传入low=0，high=array.length-1;
int pivot, p_pos, i, t;// pivot->位索引;p_pos->轴值。
if (low < high) {
p_pos = low;
pivot = array[p_pos];
for (i = low + 1; i <= high; i++) {
if (array[i] < pivot) {
p_pos++;
t = array[p_pos];
array[p_pos] = array[i];
array[i] = t;
}
}
t = array[low];
array[low] = array[p_pos];
array[p_pos] = t;
// 分而治之
quickSort(array, low, p_pos - 1);// 排序左半部分
quickSort(array, p_pos + 1, high);// 排序右半部分
}
}
运行
public static void main(String[] args) {
int[] array = {4, 44, 7, 22, 66, 5, 3};
Algorithm2 a = new Algorithm2();
a.bubbleSort(array);
// a.selectSort(array);
// a.insertSort(array);
// a.quickSort(array, 0, array.length - 1);
a.show(array);
}
展示
public void show(int[] array) {
for (int v : array) {
System.out.print(v + "\t");
}
}
