排序(新排版)
2017-04-29 本文已影响0人
RivenL
冒泡排序
void bubbleSort(int a[], int count) {
int temp = 0;
if (a == NULL) return;
if (!count) return;
for (int i=0; i<count; i++) {
for (int j=0; j<count-1; j++) {
if (a[j] < a[j+1]) {
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
插入排序
void insertSort(int a[], int count) {
int i = 1, j = 0;
int temp = 0;
for (; i<count; i++) {
j = i;
temp = a[i];
while(j>0 && temp < a[j-1]) {
a[j] = a[--j];
}
if (i != j) {
a[j] = temp;
}
}
}
二分插入排序
void binaryInsertSort(int a[], int count) {
int i, j;
int left, middle, right, temp = 0;
if (!a || count <= 0) return;
for (i=1; i<count; i++) {
j = i, temp = a[i];
left = 0, right = i-1;
while (left <= right) {
middle = left + (right - left) / 2;
if (a[middle] <= temp) {
left = middle + 1;
}
else {
right = middle - 1;
}
}
while (j>left) {
a[j] = a[--j];
}
a[j] = temp;
}
}
希尔排序
void shellSort(int a[], int count) {
int stepLength = count / 2;
int i, j, k;
if (!a || count <= 0) return;
while(stepLength) {
for (i=0; i<stepLength; i++) {
for(j=i+stepLength; j<count; j+=stepLength) {
k = j;
temp = a[k];
while(k>= stepLength && temp < a[k-stepLength]) {
a[k] = a[k-stepLength];
k -= stepLength;
}
if (k != j) a[k] = temp;
}
}
stepLength /= 2;
}
}
选择排序
void selectSort(int a[], int count) {
int i, j;
int temp, minIndex = 0;
for (i=0; i<count ; i++) {
temp = a[i];
minIndex = i;
for (j=i+1; j<count; j++) {
minIndex = a[minIndex] < a[j] ? j : minIndex;
}
if (minIndex != i) {
a[i] = a[minIndex];
a[minIndex] = temp;
}
}
}
快速排序
void quickSort(int a[], int count) {
if (!a || !count) return;
_quickSort(a, 0, count-1);
}
void _quickSort(int a[], int beginIndex, int endIndex) {
int i = beginIndex, j = endIndex;
int flag = 0;
flag = a[beginIndex];
if (beginIndex >= endIndex) return;
while(i<j) {
while(i<j && a[i]<flag) { i++; }
while(j>i && a[j]>flag) { j--; }
if (i<j) {
a[i] = a[j] ^ a[i];
a[j] = a[i] ^ a[j];
a[i] = a[j] ^ a[i];
}
}
if (start < i) {
_quickSort(a, start, i-1);
}
if (end > j) {
_quickSort(a, j+1, end);
}
}