顺序表的优缺点
1.优点： 尾插效率高，支持随机访问。
2.缺点： 中间插入或者删除效率低。
3.应用： 数组 ArrayList
插入：从插入的位置开始，后面的数据要一直往后挪
删除：从删除的位置开始，后面的数据要一直往前挪
所以性能会比较低
/**
* 插入
*/
public void insert(int[] array, int x, int index){
for (int i = array.length; i > index; i--) {
array[i] = array[i-1];
}
array[index] = x;
}
/**
* 删除
*/
public void delete(int[] array, int index){
for (int i = index; i < array.length - 1; i++) {
array[i] = array[i + 1];
}
array[array.length - 1] = 0; //用0来填充， C语言：\0 填充
}
1、交换a、b，性能分析
//做 a b 算法
int a = 5;
int b = 6;
//1. 可读性做好
int t = a; a = b; b = t;
System.out.println("1.a = " + a + ", b = " + b);
//2. 加减法
a = a + b; //11
b = a - b; //11-6=5
a = a - b; //11-5=6
System.out.println("2.a = " + a + ", b = " + b);
//3. 性能最优（没有可读性） 应用场景：无人机、跑步机
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println("3.a = " + a + ", b = " + b);
2、蛮力法：冒泡排序
从前面2个进行大小比较，进行交换。然后依次比较。
/**
* 蛮力法，冒泡排序
* 例子：3 1 5 8 2 9 4 6 7
* 时间复杂度：n*(n-1)/2 -> 趋近于n
* @param array
*/
public static void bubbleSort(int[] array){
for(int i=array.length-1;i>0;i--) {
boolean flag=true;
for (int j = 0; j < i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag=false;
}
}
if(flag){//说明后面都是排好序的，不用排序了
break;
}
}
}
3、选择排序
定位最前的一个值，然后在进行后面所有的值比较大小，找到最小的就和定位的那个值进行交换，然后依次进行。
/**
* 选择排序法
* 例子：{1,2,5,8,3,9,4,6,7}
* @param array
*/
public static void selectSort(int[] array){
for(int i=0;i<array.length-1;i++) {
int index = i;
for (int j = i+1; j < array.length; j++) {
if (array[j] < array[index]) {
index = j;
}
}
if(index!=i) {//如果已经是最小的，就不需要交换
int temp = array[index];
array[index] = array[i];
array[i] = temp;
}
}
}
4、二分查找
/**
* 二分查找，从中间一直一次往数据的两边中间查找
*/
public static int binarySearch(int[] array,int fromIndex,int toIndex,int key){
int low=fromIndex;
int high=toIndex-1;
while(low<=high){
int mid=(low+high)/2;//取中间
int midVal=array[mid];
if(key>midVal){//去右边找
low=mid+1;
}else if(key<midVal){//去左边找
high=mid-1;
}else{
return mid;
}
}
return -(low+1);//low+1表示找不到时停在了第low+1个元素的位置
}
5、快速排序（前序排序）
/**
* 快速排序 31 21 59 68 12 40
* x=31
* @param array
* @param begin
* @param end
*/
//
public static void quickSort(int[] array,int begin,int end){
if(end-begin<=0) return;
int x=array[begin];
int low=begin;//0
int high=end;//5
//由于会从两头取数据，需要一个方向
boolean direction=true;
L1:
while(low<high){
if(direction){//从右往左找
for(int i=high;i>low;i--){
if(array[i]<=x){
array[low++]=array[i];
high=i;
direction=!direction;
continue L1;
}
}
high=low;//如果上面的if从未进入，让两个指针重合
}else{
for(int i=low;i<high;i++){
if(array[i]>=x){
array[high--]=array[i];
low=i;
direction=!direction;
continue L1;
}
}
low=high;
}
}
//把最后找到的值 放入中间位置
array[low]=x;
//开始完成左右两边的操作
quickSort(array,begin,low-1);
quickSort(array,low+1,end);
}
6、分治法：归并排序（后序排序）
/**
* 归并排序
* @param array
* @param left
* @param right
*/
public static void mergeSort(int array[],int left,int right){
if(left==right){
return;
}else{
int mid=(left+right)/2;
mergeSort(array,left,mid);
mergeSort(array,mid+1,right);
merge(array,left,mid+1,right);
}
}
/**
* 归并排序
*
* 0 4 7
* 1 2 5 9 === 3 4 10 11
*
* @param array
* @param left
* @param mid
* @param right
*/
public static void merge(int[] array,int left,int mid,int right){
int leftSize=mid-left;
int rightSize=right-mid+1;
//生成数组
int[] leftArray=new int[leftSize];
int[] rightArray=new int[rightSize];
//填充数据
for(int i=left;i<mid;i++){
leftArray[i-left]=array[i];
}
for(int i=mid;i<=right;i++){
rightArray[i-mid]=array[i];
}
//合并
int i=0;
int j=0;
int k=left;
while(i<leftSize && j<rightSize){
if(leftArray[i]<rightArray[j]){
array[k]=leftArray[i];
k++;i++;
}else{
array[k]=rightArray[j];
k++;j++;
}
}
while(i<leftSize){
array[k]=leftArray[i];
k++;i++;
}
while(j<rightSize){
array[k]=rightArray[j];
k++;j++;
}
}
网友评论