数组排序
把数组中得元素，通过比较移位替换，使之变成一个有序序列 排序方式：冒泡排序，选择排序，插入排序，快速排序，希尔排序，归并排序，基数排序，堆排序。
冒泡排序
import java.util.Arrays;
//冒泡排序：数组元素 两两比较，大的往后放，经过一轮比较后，最大得元素会出现在最后面，如此往复，那么整个数组元素就有序了。
public class maoPao {
public static void main(String[] args){
int[] arr = {34,65,12,9,56,12,123,67,90};
sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr) {
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]){
int k = arr[j];
arr[j] = arr[j+1];
arr[j+1] = k;
}
}
}
}
}
选择排序
import java.util.Arrays;
//选择排序：每次拿一个元素和后面所有得元素挨个比较，小得往前放，经过一轮比交换，最小得元素会出现在最前面，如此往复，整个数组就排好序了。
public class xuanZe {
public static void main(String[] args){
int[] arr = {34,65,12,9,56,12,123,67,90};
sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr) {
for(int i=0;i<arr.length-1;i++){
for(int j=i+1;j<arr.length;j++){
if(arr[i]>arr[j]){
int k = arr[i];
arr[i] = arr[j];
arr[j] = k;
}
}
}
}
}
插入排序
import java.util.Arrays;
//直接插入排序：每次将后面一个元素，插入到之前得一个有序序列中，使之仍保持有序
public class charu {
public static void main(String[] args){
int[] arr = {34,65,12,9,56,12,123,67,90};
sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr) {
for(int i=1;i<arr.length;i++){
for(int j=i;j>0;j--){
if(arr[j]<arr[j-1]){
int k = arr[j];
arr[j] = arr[j-1];
arr[j-1] = k;
}
}
}
}
}
快速排序
import java.util.Arrays;
public class kuaiSu {
public static void main(String[] args){
int[] arr = {34,65,12,9,56,12,123,67,90};
sort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr, int left, int right) {
//得对左右两区进行递归调用
//为了分成左右两区那个索引位置
if(left<right){
int index = partition(arr,left,right);
//对左区进行递归
sort(arr,left,index-1);
//对右区进行递归
sort(arr,index+1,right);
}
}
private static int partition(int[] arr, int left, int right) {
//1.将基准数挖出形成第一个坑。
//2.由后向前找比他小的数，找到后挖出此数填到前一个坑中。
//3.由前向后找比他大或等于的数，找到后也挖出此数填到前一个坑中。
//再重复执行2，3两步骤。
//定义一个基准数
int base = arr[left];
while(left<right){
//由后向前找比他小的数，找到后挖出此数填到前一个坑中。
while(arr[right]>base&&left<right){
right--;
}
//填坑
if(left<right){
arr[left]=arr[right];
left++;
}
//3.由前向后找比他大或等于的数，找到后也挖出此数填到前一个坑中。
while(arr[left]<=base&&left<right){
left++;
}
//填坑
if(left<right){
arr[right] = arr[left];
right--;
}
}
//将基准数填到最后一个坑中
if(left==right){
arr[left] = base;
}
return left;
}
}
希尔排序
import java.util.Arrays;
//希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
//随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
public class MyTest {
public static void main(String[] args){
int[] arr = {42,12,0,-5,15,-20,56,34,89,46,13,45,61,31,3,9,14,56,13,1,-5,0,-26,85,23,12,56,};
sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr) {
//根据克努特序列选取我们第一次的增量
int jiange = 1;
while(jiange<=arr.length/3){
jiange = jiange*3+1;
}
for(int h=jiange;h>0;h=(h-1)/3){
for(int i=h;i<arr.length;i++){
for(int j=i;j>h-1;j-=h){
if(arr[j]<arr[j-h]){
int k = arr[j];
arr[j] = arr[j-h];
arr[j-h] = k;
}
}
}
}
}
}
归并排序
import java.util.Arrays;
//归并排序就是利用归并的思想实现排序的方法。
//它的原理是假设初始序列有N个记录，则可以看成是N个有序的子序列，每个子序列的长度为1，然后两两合并，
//得到N/2个长度为2或1的有序子序列，再两两归并。。。
//如此重复，直至得到一个长度为N的有序序列为止，这种排序方法称为2路归并排序。
public class MyTest2 {
public static void main(String[] args){
int[] arr = {23,56,12,57,3,0,-5,-9,90,50};
chaiFen(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
private static void chaiFen(int[] arr, int startIndex, int endIndex) {
//计算中间索引
int midIndex = (endIndex+startIndex)/2;
if(startIndex<endIndex){
chaiFen(arr,startIndex,midIndex);
chaiFen(arr,midIndex+1,endIndex);
guiBin(arr,startIndex,midIndex,endIndex);
}
}
private static void guiBin(int[] arr, int startIndex, int midIndex, int endIndex) {
//定义一个临时数组
int[] temp = new int[endIndex-startIndex+1];
//定义临时数组的起始索引
int index = 0;
//定义左边数组的起始索引
int i = startIndex;
//定义右边数组的起始索引
int j = midIndex+1;
//比较左右两个数组的元素大小，往临时数组里放
while(i<=midIndex&&j<=endIndex){
if(arr[i]<=arr[j]){
temp[index] = arr[i];
i++;
index++;
}else{
temp[index] = arr[j];
j++;
index++;
}
}
//处理剩余元素
while(i<=midIndex){
temp[index] = arr[i];
i++;
index++;
}
while(j<=endIndex){
temp[index] = arr[j];
j++;
index++;
}
//将临时数组里的元素取到原数组中
for(int h=0;h<temp.length;h++){
arr[startIndex+h] = temp[h];
}
}
}
基数排序
import java.util.Arrays;
public class MyTest3 {
public static void main(String[] args){
//基数排序：通过分配再收集的方式进行排序
int[] arr = {23,52,12,3,90,67,123,24,341,56,789,342,674,1000,34};
sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr) {
//定义二维数组，放10个桶
int[][] temp = new int[10][arr.length];
//定义统计数组
int[] count = new int[10];
//获取数组中最大值
int max = getMax(arr);
//得确定排序轮次
int len = String.valueOf(max).length();
//循环轮次
for(int i=0,n=1;i<len;i++,n*=10){
//将元素放入桶中
for(int j=0;j<arr.length;j++){
//获取每个位上的数字
int x = arr[j]/n%10;
//按每个位上的数字放入对应的桶中
temp[x][count[x]++] = arr[j];
}
//取出桶中的元素
int index = 0;
for(int h=0;h<count.length;h++){
if(count[h]!=0){
//从桶中取出元素放回原数组
for(int j=0;j<count[h];j++){
arr[index++] = temp[h][j];
}
//清除上一次统计的个数
count[h] = 0;
}
}
}
}
private static int getMax(int[] arr) {
int max = arr[0];
for(int i=1;i<arr.length;i++){
if(max<arr[i]){
max = arr[i];
}
}
return max;
}
}
堆排序
堆排序的思想： 1.将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。 2.将其与末尾元素进行交换，此时末尾就是最大值。 3.然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。 4.如此反复执行，便能得到一个有序序列了。
import java.util.Arrays;
//堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序
public class MyTest4 {
public static void main(String[] args){
int[] arr = {34,12,67,15,8,56,34,79,268,37,1,56,457,35};
sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr) {
//定义开始调整的位置
int startIndex = (arr.length-1)/2;
int size = arr.length;
//循环调调整大顶堆得方法
for(int i=startIndex;i>=0;i--){
toMaxHeap(arr,size,i);
}
//经过上面的操作后，数组已经变成一个大顶堆，将最后一个元素与第一个元素互换
for(int i=arr.length-1;i>0;i--){
int k = arr[0];
arr[0] = arr[i];
arr[i] = k;
//换完之后将剩余元素调成大顶堆
toMaxHeap(arr,i,0);
}
}
/*
* arr 要排序的数组
* size 调整的元素个数
* index 从哪里开始调整
*/
private static void toMaxHeap(int[] arr, int size, int index) {
//获取左右子节点的索引
int leftNodeIndex = 2*index + 1;
int rightNodeIndex = 2*index + 2;
//获取最大节点对应的索引
int maxNodeIndex = index;
if(leftNodeIndex<size&&arr[leftNodeIndex]>arr[maxNodeIndex]){
maxNodeIndex = leftNodeIndex;
}
if(rightNodeIndex<size&&arr[rightNodeIndex]>arr[maxNodeIndex]){
maxNodeIndex = rightNodeIndex;
}
//调换位置
if(maxNodeIndex!=index){
int k = arr[index];
arr[index] = arr[maxNodeIndex];
arr[maxNodeIndex] = k;
//调换完之后，可能会影响到下面的子树不是大顶堆，还需再次调换
toMaxHeap(arr,size,maxNodeIndex);
}
}
}
数组查找
基本查找
public class MyTest {
public static void main(String[] args) {
int[] arr = {20, 40, 2, 3, 7, 8, 1, 0, 9, 45, 30, 2,100, 200, 30, 50};
//根据元素，查询该元素，第一次在数组中出现的索引
int index= getIndex(arr,500);
System.out.println("索引是"+index);
}
private static int getIndex(int[] arr, int ele) {
int index=-1;
for (int j = 0; j < arr.length; j++) {
if(arr[j]==ele){
// return j;
index=j;
break;
}
}
return index; // -1 表示没找到
}
}
二分查找
public class erFen {
public static void main(String[] args){
//查找思想：前提条件：数组元素必须有序，二分查找：每次查找一半
int[] arr = {2,5,13,23,35,78,90,123,342,657};
int key = 657;
int index = chaZhao(arr,0,arr.length-1,key);
System.out.println("arr中"+key+"所在的索引是" + index);
int index2 = search(arr,key);
System.out.println("arr中"+key+"所在的索引是" + index2);
}
private static int chaZhao(int[] arr, int startIndex, int endIndex,int key) {
//递归实现二分查找
int midIndex = (startIndex+endIndex)/2;
if(key<arr[startIndex]||key>arr[endIndex]||startIndex>endIndex){
return -1;
}
if(arr[midIndex]<key){
return chaZhao(arr,midIndex+1,endIndex,key);
}else if(arr[midIndex]>key){
return chaZhao(arr,startIndex,midIndex-1,key);
}else{
return midIndex;
}
}
private static int search(int[] arr,int key){
//循环实现二分查找
int startIndex = 0;
int endIndex = arr.length-1;
if(key<arr[startIndex]||key>arr[endIndex]){
return -1;
}
while(startIndex<=endIndex){
int midIndex = (startIndex+endIndex)/2;
if(arr[midIndex]==key){
return midIndex;
}else if(arr[midIndex]>key){
endIndex = midIndex-1;
}else if(arr[midIndex]<key){
startIndex = midIndex+1;
}
}
return -1;
}
}
