package 未做_快速排序_归并排序_二分查找_等排序;
/*
* 快速排序
* 使用递归方法
* 把数组拆分为两个子数组加上一个基准元素:
* 1.选取最后一个元素作为基准元素，index变量记录最近一个小于基准元素的元素所在的位置，
* 初始化为start- 1，发现新的小于基准元素的元素，index加1。
* 从第一个元素到倒数第二个元素，依次与基准元素比较，
* 小于基准元素，index加1，交换位置index和当前位置的元素。
* 循环结束之后index+1得到基准元素应该在的位置，交换index+1和最后一个元素。
* 2.分别排序[start, index], 和[index+2, end]两个子数组
*
*/
public class QuickSort {
public static void main(String args[]){
int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3 };
quictSort(arr);
print(arr);
}
public static void print(int[] arr){
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]);
System.out.print(",");
}
}
public static void jiaohuan(int[] arr, int index1, int index2){
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
public static void quictSort(int[] arr){
quictSort(arr, 0 , arr.length-1);
}
public static void quictSort(int[] arr, int start, int end){
if(arr == null || end<2){
return ;//若只有1个元素或没有元素，没必要排序，停止程序
}
int part = partition(arr, start , end);//求基准元素应该所在的位置
if(part == start){
quictSort(arr, part+1, end);//递归处理 part之后的数组元素
}else if(part == end){
quictSort(arr, start, part-1);//递归处理 part之前的数组元素
}else{
quictSort(arr, start, part-1);//递归处理 part之前的数组元素
quictSort(arr, part+1, end);//递归处理 part之后的数组元素
}
}
public static int partition(int[] arr, int start, int end){
int value = arr[end];//选取最后一个元素为基准元素
int index = start-1;//为了从start---end-1 进行比较 每次index+1；
for(int i=start; i<end; i++){
if(arr[i]<value){//若元素小于最后一个元素的值 则index +1 继续向前走
index++;
if(index != i){//交换当前index 与i位置的值
jiaohuan(arr, index, i);
}
}
}
if((index+1) != end ){
jiaohuan(arr, index+1, end);
}
return index+1;//得到基准元素所在的位置
}
}
package 未做_快速排序_归并排序_二分查找_等排序;
/* 插入排序
* 升序
* 1.选取第一个元素为基准元素
* 2.若第二个元素小于基准元素，则把第二个元素插入到第一个元素的前面，把第二个元素作为基准元素
* 3.直到所有元素插入为止
*/
public class insertSort {
public static void main(String args[]){
int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3 };
Sort(arr);
print(arr);
}
public static void Sort(int[] arr){
if(arr == null || arr.length<2){
return ;
}
for(int i=1;i<arr.length;i++){
//从第i个元素开始与i之前的元素进行比较 若当前元素小于i之前的元素 则进行交换值，直到交换到第0个元素为止
int value = arr[i];
int position = i;//记录当前元素的位置
for(int j=i-1;j>=0;j--){
if(arr[j]>value){
arr[j+1]=arr[j];//若当前值前面的值大于当前值，则把前面的值赋给后面的值
position-=1;//记录value应该在的位置
}else{
break;
}
}
arr[position] = value;//把当前值放在当前位置上
}
}
public static void print(int[] arr){
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]);
System.out.print(",");
}
}
}
package 未做_快速排序_归并排序_二分查找_等排序;
//选择排序
public class SelectSort {
public static void main(String args[]){
int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3 };
Sort(arr);
print(arr);
}
public static void Sort(int[] a) {
if (a == null || a.length <= 0) {
return;
}
for (int i = 0; i < a.length; i++) {
int min = i; /* 将当前下标定义为最小值下标 */
for (int j = i + 1; j < a.length; j++) {
if (a[min] > a[j]) { /* 如果有小于当前最小值的关键字 */
min = j; /* 将此关键字的下标赋值给min */
}
}
if (i != min) {/* 若min不等于i，说明找到最小值，交换 */
int tmp = a[min];
a[min] = a[i];
a[i] = tmp;
}
}
}
public static void print(int[] arr){
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]);
System.out.print(",");
}
}
}
