1.排序分类
(1)内部排序
交换式排序 选择式排序 (选择排序法、堆排序法)插入式排序
(2)外部排序
合并排序 直接合并排序法
2.交换式排序
(1)冒泡排序
79 56 90 4 32 27 16 88 35
90 79 56 88 4 32 27 16 35
90 88 79 56 35 4 32 27 16
90 88 79 56 35 32 4 27 16
90 88 79 56 35 32 27 4 16
90 88 79 56 35 32 27 16 4
90 88 79 56 35 32 27 16 4
public class Demo{
public static void main(String[] args){
int arr[] = {1,6,0,-1,9,-100,90};
Bubble bubble = new Bubble();
bubble.sort(arr);
for(int i = 0;i<arr.length;i++){
System.out.println(arr[i] + " ");
}
}
for(int ij= 0;j<arr.length;j++){
System.out.print(arr[j] + " ");
}
}
class Bubble{
public void Sort(int arr[]){
int temp = 0;
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}
(2)快速排序法
基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的数据都比另外一部分的所有数据小,然后按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行。
class QuickSort{
public void sort(int left,int right,int[] array){
int l = left;
int r = right;
int pivot = array[(left+right)/2];
int temp= 0;
while(l<r){
while(array[1] < pivot) l++;
while(array[r] > pivot) r--;
if(l>=r) break;
temp = array[1];
array[1] = array[r];
array[r] = temp;
if(array[1] == pivot) --r;
if(array[r] == pivot) ++l;
}
if (l==r){
l++;r--;
}
if(left < r) sort(left,r,array);
if(right >1) sort(l,right,array);
}
}
3.选择式式排序
8 3 2 1 7 4 6 5
1 3 2 8 7 4 6 5
1 2 3 8 7 4 6 5
1 2 3 8 7 4 6 5
1 2 3 4 8 7 6 5
1 2 3 4 7 8 6 5
1 2 3 4 5 8 6 7
1 2 3 4 5 6 8 7
1 2 3 4 5 6 7 8
Select select = new Select();
select.sort(arr1);
for(int i = 0;i<arr1.length;i++){
System.out.println(arr1[i] + " ");
}
class Select{
public void Sort(int arr[]){
int temp = 0;
for(int j = 0;j<arr.length-1;j++){
int min = arr[j];
int minIndex = j;
for(int k=j+1;k<arr.length;k++){
if(min > arr[k]){
min = arr[k];
minIndex = k;
}
}
temp =arr[j];
arr[j] = arr[minIndex];
arr[minIndex] = temp;
}
}
4.插入式排序
(1)插入排序法
基本思想:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含n-1个元素,排序过程中,每次从无序表中取出第一个元素,把他的排序码依次与有序表元素的排序码进行比较,将他插入到有序表中的适当位置,使之成为新的有序表。
17 3 25 14 20 9
3 17 25 14 20 9
3 17 25 14 20 9
3 14 17 25 20 9
3 14 17 20 25 9
3 9 14 17 20 25
class InsertSort{
public void sort(int arr[]){
for(int i=1;i<arr.length;i++){
int insertVal = arr[i];
int index = i-1;
while(index>=0&&insertVal < arr[index]){
arr[index + 1] = arr[index];
index --;
}
arr[index + 1] = insertVal;
}
}
}
(2)希尔排序法
(3)二叉树排序法
5.查找
(1)顺序查找
(2)二分查找
思路:找到数组的中间数(midVal),和你要查找的数finalVal进行比较,如果midVal>findVal,则说明findVal在数的左边,就把该数组二分。
class BinaryFind{
public void find (int leftIndex,int rightIndex,int val,int arr[]){
int midIndex = (rightIndex+leftIndex)/2;
int midVal = arr[midIndex];
if(rightIndex >= leftIndex){
if(midVal > val){
find (leftIndex,midIndex-1,val,arr);
}else if (midVal <val){
find (midIndex +1,rightIndex,val,arr);
}else if (midVal == val){
System.out.println(“找到下标”+midIndex);
}
}
}
}