spring
1.冒泡排序
/* 冒泡排序 */
for (int end = cnt - 1; end > 0 ; end --) {
// 优化-减少已排序部分的比较
int startIndex = 1;
for (int begin = 1; begin <= end; begin ++) {
if (array[begin - 1] < array[begin]) {
int tmp = array[begin - 1];
array[begin - 1] = array[begin];
array[begin] = tmp;
startIndex = begin;
}
}
end = startIndex;
}
2.选择排序
// - 比较后，记录最大索引，最后进行交换。
for (int end= cnt - 1; end > 0; end--) {
int maxIndex = 0;
for (int begin = 1; begin <= end; begin++) {
if(array[maxIndex] <= array[begin]) {
maxIndex = begin;
}
}
int tmp = array[end];
array[end] = array[maxIndex];
array[maxIndex] = tmp;
}
3.堆排序
int array[] = {9, 5, 2, 7};
int heapSize = array.length;
void sort() {
heapify();
while (heapSize > 1) {
int tmp = array[heapSize - 1];
array[heapSize - 1] = array[0];
array[0] = temp;
heapSize--;
siftDown(0);
}
}
// 建堆
void heapify() {
for (int i = (heapSize >> 1) - 1; i >= 0; i --) {
siftDown(i);
}
}
// 自下而上的下滤
void siftDown(int index) {
int current = array[index];
int half = heapSize >> 1;
while (index < half) {
int childIndex = (index << 1) + 1;
int child = array[childIndex];
int rightIndex = childIndex + 1;
if (rightIndex < heapSize && array[rightIndex] > child) {
child = array[childeIndex = rightIndex];
}
if (current >= child) break;
array[index] = child;
index = childIndex;
}
array[index] = current;
}
4.插空排序
- 代码解析见注释。
int a[5]={9, 8, 10, 2, 20};
// key为每次被拿出的值（也就是初始提供“空”的值），j为要比较到的最大索引
int key,j;
// 直接插入排序
for (int i=1; i<5; i++) {
// 取出当前要比较项
key=a[i];
// 和直到索引j位置的元素逐一比较
for (j=i-1; j>=0&&a[j]>key; j--) {
// j为更新出来的新空
a[j+1]=a[j];
}
// 因为循环结束时进行一次j--操作，所以下面要+1
// j+1为最后留给key的空
a[j+1]=key;
}
// 另一种写法
for (int begin=1; begin < 5; begin++) {
// 记录当前索引（当前空位）
int cur = begin;
int val = a[cur];
// 和直到索引j位置的元素逐一比较
while (cur > 0 && val > a[cur - 1]) {
// j为更新出来的新空
a[cur] = a[cur - 1];
cur --;
}
a[cur] = val;
}
- 二分查找
// 返回找到的元素对应的索引，没找到返回-1
int binarySearch(int array[], int v) {
if (array == null || array.length == 0) {
retrun -1;
}
int begin = 0;
int end = array.length;
while (begin < end) {
int mid = (begin + end) >> 1;
if (v > array[mid]) {
begin = mid + 1;
} else if (v < array[mid]) {
end = mid;
} else {
return mid;
}
}
return -1;
}
- 结合二分查找优化插空排序
void insertSort(int [] array) {
for (int begin = 1; begin < array.length; begin++) {
insert(begin, search(begin));
}
}
// 执行插入的元素位移操作
void insert(int source, int target) {
int v = array[source];
for (int i = source; i > target; i --) {
array[source] = array[source - 1];
}
array[target] = v;
}
// 用二分法查找当前取出的元素在已排好序部分对应的插入位置
int search(int index) {
int v = array[index];
int begin = 0;
int end = index;
while (begin < end) {
int mid = (begin + end) >> 1;
if (v >= array[mid]) {
begin = mid + 1;
} else {
end = mid;
}
}
return begin;
}
5.归并排序
int[] array = {9, 5, 2, 7};
void mergeSort() {
sortRecursive(0, array.length);
}
void sortRecursive(int begin, int end) {
// 数组只剩一个元素，不能再分了
if (end - begin < 2) return;
int mid = (begin + end) >> 1;
sortRecursive(begin, mid);
sortRecursive(mid, end);
merge(begin, mid, end);
}
// 用来存放左边排好序部分的备用数组
int leftArray[] = new int[array.length >> 1];
void merge(int begin, int mid, int end) {
int lp = 0, le = mid - begin;
int rp = mid, re = end;
int ap = begin;
for (int i = 0; i < le; i ++) {
leftArray[i] = array[begin + i];
}
// 只要左边结束了，整个排序就结束了
while (lp < le) {
if (rp < re && array[rp] < leftArray[lp]) {
array[ap++] = array[rp++];
} else {
array[ap] = leftArray[lp];
ap ++;
lp ++;
}
}
}
6.快速排序
int[] array = {9, 5, 2, 7};
void pivotSort() {
pivotRecursive(0, array.length);
}
void pivotRecursive(int begin, int end) {
if (end - begin < 2) return;
// 找到轴点的位置
int pivot = pivotIndex(begin, end);
// 递归轴点左
pivotRecursive(begin, pivot);
// 递归轴点右
pivotRecursive(pivot + 1, end);
}
int pivotIndex(int begin, int end) {
// 优化：为了轴点左右数据更加均衡，随机选择轴点
int random = random(end - begin);
int tmp = array[begin];
array[begin] = array[random];
array[random] = tmp;
int v = array[begin];
// 因为end是从array.length开始的，所以要--
end--;
// 嵌套while循环实现左右交替执行
while (begin < end) {
while (begin < end) {
if (array[end] > v) {
end--;
} else {
array[begin++] = array[end];
break;
}
}
while (begin < end) {
if (array[begin] < v) {
begin++;
} else {
array[end--] = array[begin];
break;
}
}
}
array[begin] = v;
return begin
}
7.希尔排序
- 可看作是对插空排序的优化
int[] array = {9, 5, 2, 7};
void shellSort() {
int[] steps = step(array.length);
for (int i = 0; i < steps.length; i ++) {
int step = steps[i];
for (int col = 0; col < step; col ++) {
for (int begin = col + step; begin < array.length; begin += step) {
int cur = begin;
int v = array[cur];
while (cur > col && v > array[cur - step]) {
array[cur] = array[cur - step];
cur -=step;
}
arrau[cur] = v;
}
}
}
}
// 创建步长数组
int[] step(int step) {
int[] steps = new int[];
while ((step >>= 1) > 0) {
steps.add(step)
}
return step;
}
8.计数排序
- 中心思想：用空间换时间
- 只适用于一定范围内的整数排序
int[] array = {9, 5, 2, 7};
// 仅支持正整数版本
// 找出最大值
int max = array[0];
for (int i = 1; i < array.length; i ++) {
if (array[i] > max) {
max = array[i];
}
}
// 创建计数数组
int[] counts = new int[max + 1];
for (int i = 0; i < array.length; i ++) {
conuts[array[i]] += 1;
}
// 输出排好序的数组
int index = 0;
for (int i = 0; i < counts.length; i ++) {
while ((counts[i]--) > 0) {
array[index++] = i;
}
}
// 优化版本，支持负整数(包含整数属性排序的自定义对象也可以)
// 找出最大值，最小值
int max = array[0];
int min = array[0];
for (int i = 1; i < array.length; i ++) {
if (array[i] > max) {
max = array[i];
}
if (array[i] < min) {
min = array[i];
}
}
// 计数数组
int[] counts = new int[max - min + 1];
for (int i = 0; i < array.length; i ++) {
conuts[array[i] - min] += 1;
}
// 累加次数
for （int i = 1; i < counts.length; i++) {
counts[i] += counts[i - 1];
}
// 从后往前遍历元素，将它放到有序数组中的合适位置
int newArray = new int[array.length];
for (int i = array.length - 1; i >=0; i --) {
newArray[--counts[array[i] - min]] = array[i];
}
// 将有序数组赋值到array
for (int i = 0; i < array.length; i ++) {
array[i] = newArray[i];
}
9.基数排序
- 数据从低位到高位按位排序
- 排序用计数排序
int[] array = {9, 5, 2, 7};
// 仅支持正整数版本
// 找出最大值
int max = array[0];
for (int i = 1; i < array.length; i ++) {
if (array[i] > max) {
max = array[i];
}
}
// 创建计数数组
int[] counts = new int[max + 1];
for (int devider = 1; devider < max; devider * 10) {
countingSort(devider);
}
void countingSort(int devide) {
// 计数数组
int[] counts = new int[10];
for (int i = 0; i < array.length; i ++) {
conuts[array[i] / devide % 10] += 1;
}
// 累加次数
for （int i = 1; i < counts.length; i++) {
counts[i] += counts[i - 1];
}
// 从后往前遍历元素，将它放到有序数组中的合适位置
int newArray = new int[array.length];
for (int i = array.length - 1; i >=0; i --) {
newArray[--counts[array[i] / devide % 10]] = array[i];
}
// 将有序数组赋值到array
for (int i = 0; i < array.length; i ++) {
array[i] = newArray[i];
}
}
10.桶排序
- 自定义规则
- 按规则尽量均匀分布数据到每个桶
- 对桶内数据排序
- 将桶内数据串起来
以上均为伪代码，仅提供思路
整体测试代码
#import <Foundation/Foundation.h>
void initArray(int array[],int cnt);
void selectSortForArray(int array[],int cnt);
void showArray(int array[],int cnt);
void initArray(int array[],int cnt)
{
for(int i= 0;i<cnt;i++)
array[i] = arc4random() % 100;
}
void selectSortForArray(int array[],int cnt)
{
/*for (int i = 0; i<cnt-1; i++){
for (int j = i+1; j<cnt; j++)
{if (array[i] < array[j]) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}}}*/
//****************这样每次比较后都交换元素位置**********
for (int i= 0;i<cnt-1;i++){
for (int j=i + 1;j<cnt;j++){
if(array[i]<array[j]){
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
}
// }
//*****************这样每次比较只记住索引，内循环遍历一次完成后再交换（减少交换次数），*********
for (int i = 0; i < cnt - 1; i++) {
int tmp = 0;
for (int j = i + 1; j < cnt; j++) {
if (array[i] < array[j]) {
tmp = j;
}
int c = array[i];
array[i] = array[tmp];
array[tmp] = c;
}
}
/* 冒泡排序 */
for (int i = 0; i < cnt - 1; i ++) {
for (int j = 0; j < cnt - i - 1; j ++) {
if (array[j] < array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
}
void showArray(int array[],int cnt)
{
for (int i = 0; i<cnt; i++) {
printf("%d ",array[i]);
}
printf("\n");
}
int main(int argc, const char * argv[])
{
@autoreleasepool {
// insert code here...
// NSLog(@"Hello, World!");
//
int array[10] = {0};
initArray(array, 10);
showArray(array,10);
selectSortForArray(array, 10);
showArray(array,10);
// C-实现 插空排序
int a[5]={9,8,10,2,20};
int key,j;// key为每次被拿出的值（也就是初始提供“空”的值），j为要比较到的最大索引
for (int i=1; i<5; i++) {// 直接插入排序
key=a[i];// 取出当前要比较项
for (j=i-1; j>=0&&a[j]>key; j--) {// 和直到索引j位置的元素逐一比较
a[j+1]=a[j];// j为更新出来的新空（但是只要进了循环，此次循环结束就会进行一次j--操作，所以下面要+1）
}
a[j+1]=key;// j+1为最后留给key的空
}
for (int i=0; i<5; i++) {
// NSLog(@"%i",a[i]);
}
// OC实现
// NSMutableArray *array=[NSMutableArray arrayWithObjects:@9,@8,@10,@2,@20, nil];
// id key;
// NSInteger j;
// for (NSInteger i=1; i<array.count; i++) {
// key=[array objectAtIndex:i];//取到每一个待插入的数据,从a[1]开始查找
// for (j=i-1; j>=0&&array[j]>key; j--) {
// // 如果之前的数比key大,就将这个数向后移动一个位置,留出空来让key插入就像整牌一样
//
// [array exchangeObjectAtIndex:j+1 withObjectAtIndex:j];//交换
// }
// [array replaceObjectAtIndex:j+1 withObject:key];
// }
// for (key in array) {
// NSLog(@"%@",key);
// }
printf("\n");
}
return 0;
}
