冒泡，选择，插入，快速，归并这些个排序 ，说实在的 面试中问到的概率很大，但是实际开发中几乎用不到。为了更好的工作 ，小伙子你要加油
冒泡排序
冒泡排序的就是让大的数向后冒，让小的数向前冒。通过前后两个数据比较，不断将大的元素移动到尾部
//冒泡排序
//冒泡排序的就是让大的数向后冒，让小的数向前冒。通过前后两个数据比较，不断将大的元素移动到尾部。
private void initList() {
int[] numbers = new int[]{1, 5, 8, 2, 3, 9, 4, 19, 12, 7, 20};
for (int i = 0; i < numbers.length - 1; i++) {
for (int j = 0; j < numbers.length - 1 - i; j++) {
if (numbers[j] > numbers[j + 1]) {
int temp = numbers[j];
numbers[j] = numbers[j + 1];
numbers[j + 1] = temp;
}
}
}
for (int i = 0; i < numbers.length - 1; i++) {
Log.i("stf", "---numbers--->" + numbers[i]);
}
}
选择排序
选择排序就是把无序区的最小元素与首元素互换位置，然后将有序区的区间扩大一位，直到所有无序区都变成有序区。
// 选择排序就是把无序区的最小元素与首元素互换位置，然后将有序区的区间扩大一位，直到所有无序区都变成有序区。
private void initList2() {
int[] arr = {-10, 2, 3, 246, -100, 0, 5};
for (int i = 0; i < arr.length - 1; i++) {
int k = i;
//位置还不确定的数据
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[k]) {
k = j;
//遍历找到比k小的索引，然后把j赋给k；
}
}
if (i != k) {
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
for (int i = 0; i < arr.length - 1; i++) {
Log.i("stf", "---arr--->" + arr[i]);
}
}
插入排序
插入排序是把数组分为有序区和无序区两块，然后将无序区的指定索引的数插入到有序区的指定位置，假设第0个元素是已经排序好的，无序区第一次循环从1开始遍历，设置一个temp，找到要插入的位置，把temp插入到有序区指定位置。
private void initList4() {
int []arr= {-10, 2, 3, 246, -100, 0, 5};
int j=0;
for(int i=1;i<arr.length;i++) {
int temp=arr[i];
//temp存放将要插入的数据
if(arr[i]<arr[i-1]) {
for( j=i-1;j>=0&&arr[j]>temp;j--) {
arr[j+1]=arr[j];
//temp的位置空出来，把第j个的值赋给第j+1个；
}
arr[j+1]=temp;
}
}
for (int i = 0; i < arr.length - 1; i++) {
Log.i("stf", "---arr--->" + arr[i]);
}
}
快速排序
快速排序主要思想方法有两个：一趟排序和分治；一趟排序完成数组的第一次排序，设置一个键值data,找到对应正确的位置，data的值插进去；分治就是用分而治之的思想，将键值左右两侧分为两个部分，再调用递归，将左边的部分再分为两个部分，将右边的部分再分为两个部分，依此类推，直到将数组排列完。
private void initList5() {
int[] arr = { -10, 2, 3, 246, -100, 0, 5 };
QuickSort(arr, 0, arr.length - 1);
}
public static int PartSort(int arr[], int low, int high) {
int data = arr[low];
/*
* 一次遍历的方法：插空法 定义一个data将arr[low]存起来，并把这个位置挖空
*/
while (low < high) {
while (low < high && arr[high] >= data) {
high--;
}
arr[low] = arr[high];
/**
* 从high，也就是后面往前遍历 找到比键值小的数据 插入到前面留下的空中 high位再次留下空来
*/
while (low < high && arr[low] <= data) {
low++;
}
arr[high] = arr[low];
}
arr[low] = data;
/*
* 循环退出后 low和high重合 将将键值赋给第low，并将low返回
*/
return low;
}
public static void QuickSort(int arr[], int low, int high) {
if(low<high) {
//防止发生栈溢出异常
int index = PartSort(arr, low, high);
QuickSort(arr, low, index - 1);
QuickSort(arr, index + 1, high);
}
}
归并排序
归并排序要点有两个：对于两个有序数组的合并；递归思想。合并两个有序数组要定义一个新数组temp来存放合并后的数组，并通过判断条件让新的数组在合并后成为有序数组。归并的时候让数组调用自己，一步步将数组的长度变小，当子数组被分治到只有一个元素的时候，子数组也就是有序数组，这时候可以调用合并有序数组的方法，整个数组也就完成了排序。
private void initList6() {
int[] arr = { -10, 2, 3, 246, -100, 0, 5 };
MergeSort(arr, 0, arr.length-1);
}
public static void merge(int arr[],int low,int mid,int high ) {
int temp[]=new int[high-low+1];
/*
* 创建数组的三种方法
* 1.new int[数组长度];
* 2.｛数组的数据｝；
* 3.new int[]{数组的数据}
*/
int i=low;
//第一个数组的首索引
int j=mid+1;
//第二个数组的首索引
int k=0;
//新数组的首索引
while(i<=mid&&j<=high) {
if(arr[i]<arr[j]) {
temp[k++]=arr[i++];
}
else {
temp[k++]=arr[j++];
}
}
//把两个有序数组合并到新数组中
while(i<=mid) {
temp[k++]=arr[i++];
}
while(j<=high) {
temp[k++]=arr[j++];
}
for(int n=0;n<temp.length;n++) {
arr[n+low]=temp[n];
}
//排序好的数组放置在temp中，要将其复制到arr中。
}
public static void MergeSort(int arr[],int low,int high) {
int mid=(low+high)/2;
if(low<high) {
//防止栈溢出异常
MergeSort(arr,low,mid);
MergeSort(arr,mid+1,high);
merge(arr, low, mid, high);
}
}
网友评论