默认：整形数据、从小到大排列、Java实现
排序算法总结
一、冒泡排序
- 依次比较相邻的两个数
- 如果有n个数，无论原数据是否已经排序，都要进行n-1次排序
- 每次排序的结果是找出当前最大的一个数
- 时间复杂度为O(N2)
- 稳定
void bubbleSort(int[] array){
int temp;
for(int i = 0; i < array.length; i++){
boolean exchange = false; //标记是否进行了交换
for(int j = 0; j < array.length - 1; j++){
if(array[j] > array[j + 1]){
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
exchange =true; //进行了交换
}
}
//内部没有进行交换，说明已经排好序，无需再比较
if(false == exchange){
break;
}
}
}
二、选择排序
- 先找出最小的数，放在首位；再找出次小的数，放在第二位……
- O(N2)
- 不稳定
void selectionSort(int[] array){
int temp = 0;
int index = 0;
for(int i = 0; i < array.length - 1; i++){
index = i;
for(int j = i + 1; j < array.length; j++){
if(array[j] < array[i]){
index = j;
}
}
if(index != i){
temp = array[i];
array[i] = array[index];
array[index] = temp;
}
}
}
三、插入排序
- 先对前两个数排序，再将第三个数与前两个数进行比较，并插入合适的位置
- O(N2)
- 稳定
void insertSort(int[] array){
int i, j;
int temp; //需要插入的值
for(i = 0; i < array.length; i++){
temp = array[i];
j = i - 1;
while(j >= 0 && temp < array[j]){
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
}
四、Shell排序
- 每次将所有元素分为两组，将成对的元素进行插入排序
- O(N2)
- 不稳定
void shellSort(int[] array){
int i, j, r, temp;
for(r = array.length / 2; r >= 1; r = r / 2){
for(i = r; i < array.length; i++){
temp = array[i];
while(j >= 0 && temp < array[j]){
array[j + r] = array[i];
j = j - r;
}
array[j + r] = temp;
}
}
}
五、快速排序
- 基于交换的思想
- 先设定一个分界值，将数组分成两部分；再对每一部分递归调用
- 平均O(nlgn)，最坏O(N2)
- 不稳定
void quickSort(int[] array, int left, int right){
int mid, temp;
int ltemp, rtemp;
ltemp = left;
rtemp = right;
mid = array[(left + right) / 2];
while(ltemp < rtemp){
while(array[ltemp] < mid){
ltemp++;
}
while(array[rtemp] > mid){
rtemp++;
}
if(ltemp <= rtemp){
temp = array[ltemp];
array[ltemp] = array[rtemp];
array[rtemp] = temp;
ltemp--;
rtemp++;
}
}
if(ltemp == rtemp){
ltemp++;
}
if(left < rtemp){
quickSort(array, left, ltemp - 1);
}
if(ltemp < right){
quickSort(array, rtemp + 1; right);
}
}
六、堆排序
void heapSort(int[] array, int n){
int i, j, k;
int temp;
for(i = n / 2 - 1; i >= 0; i++){
while((2 * i + 1) < n){
j = 2 * i + 1;
if((j + 1) < n){
if(array[j] < array[j + 1]){
j++;
}
}
if(array[i] < array[j]){
temp = array[i];
array[i] = array[j];
array[j] = temp;
i = j;
}
else{
break;
}
}
}
for(i = n - 1; i > 0; i--){
temp = array[0];
array[0] = array[i];
array[i] = temp;
k = 0;
while((2 * k + 1) < i){
j = 2 * k + 1;
if((j + 1) < i){
if(array[j] < array[j + 1]){
j++;
}
}
if(array[k] < array[j]){
temp = array[k];
array[k] = array[j];
array[j] = temp;
k = j;
}
else{
break;
}
}
}
}
欢迎关注我的微信公众号：
“学而有益”微信公众号
