1.插入排序

1.1直接插入排序

// 插入排序
void insertSort(int array[], int length)
{int i, j, key;for (i = 1; i < length; i++){key = array[i];// 把i之前大于array[i]的数据向后移动for (j = i - 1; j >= 0 && array[j] > key; j--){array[j + 1] = array[j];}// 在合适位置安放当前元素array[j + 1] = key;}
}

1.2shell排序

// shell排序
void shellSort(int array[], int length)
{int key;// 增量从数组长度的一半开始,每次减小一倍for (int increment = length / 2; increment > 0; increment /= 2)for (int i = increment; i < length; ++i){key = array[i];// 对一组增量为increment的元素进行插入排序for (int j = i - increment; j >= 0 && array[j] > key; j -= increment){array[j+increment] = array[j];}// 在合适位置安放当前元素array[j+increment] = key;}
}

2.交换排序

2.1冒泡排序

//冒泡排序
void bubble_sort(int a[], int length)
{int i, j, tag;for(i = length - 1; i > 0; i--)//不断把前面无序区最大元素移到后面有序区{tag = 1;//标志位for(j = 0; j < i; j++)//前面无序区最大元素不断向后移{if(a[j] > a[j + 1]){a[j] ^= a[j + 1];a[j + 1] ^= a[j];a[j] ^= a[j+1];tag = 0;}}if(tag == 1){break;}}
}

2.2快速排序

// 对一个给定范围的子序列选定一个枢纽元素,执行完函数之后返回分割元素所在的位置,
// 在分割元素之前的元素都小于枢纽元素,在它后面的元素都大于这个元素
int partition(int array[], int low, int high)
{// 采用子序列的第一个元素为枢纽元素int pivot = array[low];while (low < high){// 从后往前在后半部分中寻找第一个小于枢纽元素的元素while (low < high && array[high] >= pivot)--high;// 将这个比枢纽元素小的元素交换到前半部分array[low] = array[high];// 从前往后在前半部分中寻找第一个大于枢纽元素的元素while (low < high && array[low] <= pivot)++low;// 将这个比枢纽元素大的元素交换到后半部分array[high] = array[low];}array[low] = pivot;// 返回枢纽元素所在的位置return low;
}
// 快速排序
void quickSort(int array[], int low, int high)
{if (low < high){int n = partition(array, low, high);quickSort(array, low, n);quickSort(array, n + 1, high);}
}

3.选择排序

3.1直接选择排序

//直接选择排序
void selectSort(int array[],int nLength)
{int i,j,k;for(i = 0; i < nLength - 1; i++){k = i;for(j = i+1; j < nLength; j++){if(array[j] < array[k])k = j;}if(k != i)swap(&array[k],&array[i]);}
}

3.2堆排序

         n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质（简称为堆性质）：

// array是待调整的堆数组,i是待调整的数组元素的位置,length是数组的长度
void heapAdjust(int array[], int i, int nLength)
{int nChild, nTemp;for (nTemp = array[i]; 2 * i + 1 < nLength; i = nChild){// 子结点的位置是 父结点位置 * 2 + 1nChild = 2 * i + 1;// 得到子结点中较大的结点if (nChild != nLength - 1 && array[nChild + 1] > array[nChild])++nChild;// 如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点if (nTemp < array[nChild])array[i] = array[nChild];else// 否则退出循环break;}// 最后把需要调整的元素值放到合适的位置array[i] = nTemp;
}
// 堆排序算法
void heapSort(int array[], int length)
{//建立大顶堆for (int i = length / 2 - 1; i >= 0; --i)heapAdjust(array, i, length);// 从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素for (int j = length - 1; j > 0; --j){// 把第一个元素和当前的最后一个元素交换,// 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的swap(&array[0], &array[j]);// 不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值heapAdjust(array, 0, j);}
}

4.归并排序

void merge(int array[],int start,int mid,int end)
{int i,j,k;i = start;j = mid + 1;k = 0;int * p = (int *)malloc((end - start + 1) * sizeof(int));while((i <= mid) && (j <= end)){if(array[i] < array[j])p[k++] = array[i++];elsep[k++] = array[j++];}while(i <= mid)p[k++] = array[i++];while(j <= end)p[k++] = array[j++];k = 0;while(start <= end)array[start++] = p[k++];free(p);
}
//归并排序
void mergeSort(int array[],int start,int end)
{if(start < end){int i = (start + end) / 2;mergeSort(array,start,i);mergeSort(array,i+1,end);merge(array,start,i,end);}
}

5.计数排序和基数排序      

//计数排序
//nMaxValue为数组array中最大值
void countingSort(int array[],int nMaxValue,int nLength)
{int i;int *pTemp = (int *)malloc((nMaxValue + 1) * sizeof(int));int *pResult = (int *)malloc((nLength + 1) * sizeof(int));for(i = 0; i <= nMaxValue; i++)pTemp[i] = 0;// 此过程记录每一个元素的个数for(i = 0; i < nLength; i++)pTemp[array[i]]++;// 此过程确定小于元素x的元素的个数for(i = 1; i <= nMaxValue; i++)pTemp[i] += pTemp[i-1];for(i = nLength-1; i >= 0; i--){pResult[pTemp[array[i]]] = array[i];pTemp[array[i]]--;}for(i = 1; i <= nLength; i++)array[i-1] = pResult[i];
}

//基数排序
//nMaxBit为数字中的最高位数，如最大数为235，则nMaxBit为3
void radixSort(int *array, int nLength ,int nMaxBit)
{int i,j;int temp[10];int nTmp;int nRadix = 1;int *pResult = (int *)malloc(nLength * sizeof(int)); for(j = 1; j <= nMaxBit; j++){// 以下和计数排序一样for(i = 0; i < 10; i++)temp[i] = 0;// 此过程记录每一个元素的个数for(i = 0; i < nLength; i++){nTmp = (array[i] / nRadix) % 10;temp[nTmp]++;}// 此过程确定小于元素x的元素的个数for(i = 1; i < 10; i++)temp[i] += temp[i-1];for(i = nLength-1; i >= 0; i--){nTmp = (array[i] / nRadix) % 10;temp[nTmp]--;pResult[temp[nTmp]] = array[i];}for(i = 0; i < nLength; i++)array[i] = pResult[i];nRadix *= 10;}
}