1.冒泡排序法
冒泡排序稳定的
#include #define SIZE 8 void bubble_sort(int a[],int n); void bubble_sort(int a[],int n) { int i,j,temp; for(i=0;i<n-1;i++) for(j=0;ja[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } int main() { int number[SIZE]={95,45,15,78,84,51,24,12}; int i; bubble_sort(number,SIZE); for(i=0;i<SIZE;i++){ printf("%d",number[i]); printf("\n"); } 2.选择排序法 选择排序不是稳定的 void Swap(int* data1, int* data2) { int temp = *data1; *data1 = *data2; *data2 = temp; } /******************************************************** *函数名称：SelectionSort *参数说明：a[] 无序数组； * n为无序数据个数 *说明： 选择排序 *********************************************************/ void SelectionSort(int* a, int n) { for (int i = 0; i < n - 1; i++) //从第一个位置开始 { int index = i; for (int j = i + 1; j < n; j++) //寻找最小的数据索引 if (a[j] < a[index]) index = j; if (index != i) //如果最小数位置变化则交换 Swap(&a[index], &a[i]); } }3.插入排序法
插入排序是稳定的
#include using namespace std; void InsertionSort(int a[], int n) { int j,temp,p; for (p = 1;p < n;p++) { temp = a[p]; for (j = p;j > 0 && a[j - 1] > temp;j--) a[j] = a[j - 1]; a[j] = temp; } } int main() { int b[] = {34,8,64,51,32,21}; InsertionSort(b,6); for (int m = 0;m <= 5;++m) cout << b[m] << " "; system("pause"); return 0; }4.希尔排序法
希尔排序是不稳定的
#include #include using namespace std; void ShellSort(int a[], int n) { int i, j, Increment, temp; for(Increment=n/2;Increment>0;Increment/=2) for (i = Increment;i < n;i++) { temp = a[i]; for (j = i;j >= Increment;j -= Increment) { if (a[j - Increment] > temp) a[j] = a[j - Increment]; else break; } a[j] = temp; } } int main() { int b[] = {9,8,7,6,5,4,3,2,1}; ShellSort(b,9); for (auto c : b) cout << c << " "; system("pause"); return 0; }5.堆排序
堆排序是不稳定的
#include using namespace std; void swap(int *x, int *y) { int temp = *x; *x = *y; *y = temp; } int leftchild(int i) { return 2 * i + 1; } void pecdown(int a[], int i, int n) { int child, temp; for (temp = a[i];leftchild(i) < n;i = child) { child = 2 * i + 1; if (child != n - 1 && a[child + 1] > a[child]) child++; if (temp < a[child]) a[i] = a[child]; else break; } a[i] = temp; } void HeapSort(int a[], int n) { int i; for (i = n / 2;i >= 0;i--)//建立堆// pecdown(a,i,n); for (i = n - 1;i > 0;i--) { swap(&a[0], &a[i]); pecdown(a, 0, i); } } int main() { int b[] = {142,543,123,65,453,879,572,434,111,242,811,102}; HeapSort(b,12); for (auto c : b) cout << c << " "; system("pause"); return 0; }6.归并排序
归并排序是稳定的
#include #include #include using namespace std; string error(const string &x) { return x; } void Merge(int a[], int tempa[], int lpos, int rpos, int rightend) { int i, leftend, NumSum, tempos; leftend = rpos - 1; tempos = lpos; NumSum = rightend - lpos + 1; while (lpos <= leftend && rpos <= rightend) if (a[lpos] <= a[rpos]) tempa[tempos++] = a[lpos++]; else tempa[tempos++] = a[rpos++]; while (lpos <= leftend) tempa[tempos++] = a[lpos++]; while (rpos <= rightend) tempa[tempos++] = a[rpos++]; for (i = 0;i < NumSum;i++, rightend--) a[rightend] = tempa[rightend]; } void MSort(int a[], int tempa[], int left, int right) { int center; if (left < right) { center = (left + right) / 2; MSort(a,tempa,left,center); MSort(a, tempa, center + 1, right); Merge(a,tempa,left,center+1,right); } } void MergeSort(int a[], int n) { int *tempa; tempa = (int *)malloc(n*sizeof(int)); if (tempa != NULL) { MSort(a, tempa, 0, n - 1); free(tempa); } else error("out of space"); } int main() { int b[] = {142,543,123,65,453,879,572,434,111,242,811,102}; MergeSort(b,12); for (auto c : b) cout << c << " "; system("pause"); return 0; }7.快排序
快排序是不稳定的
#include #include #include using namespace std; void InsertionSort(int v[], int n) { int j, temp, p; for (p = 1;p < n;p++) { temp =v[p]; for (j = p;j > 0 && v[j - 1] > temp;j--) v[j] = v[j - 1]; v[j] = temp; } } void swap(int *x, int *y) { int temp = *x; *x = *y; *y = temp; } int median3(int a[], int left, int right) { int center = (left+right) / 2; if (a[left] > a[center]) swap(&a[left], &a[center]); if (a[left] > a[right]) swap(&a[left],&a[right]); if (a[center] > a[right]) swap(&a[center], &a[right]); swap(&a[center],&a[right-1]); return a[right-1]; } void Qsort(int a[], int left, int right) { int i, j; int pivot; if (left + 3 <= right) { pivot = median3(a, left, right); i = left, j = right - 1; for (;;) { while (a[++i] < pivot) {} while (a[--j] > pivot) {} if (i < j) swap(&a[i], &a[j]); else break; } swap(&a[i], &a[right - 1]); Qsort(a, left, i - 1); Qsort(a, i + 1, right); } else InsertionSort(a + left, right - left + 1); } int main() { int b[] = {142,543,123,65,453,879,572,434,111,242,811,102}; Qsort(b,0,11); for (auto c : b) cout << c << " "; system("pause"); return 0; } #include using namespace std; void Qsort(int a[], int low, int high) { if(low >= high) { return; } int first = low; int last = high; int key = a[first];/*用字表的第一个记录作为枢轴*/ while(first < last) { while(first < last && a[last] >= key) { --last; } a[first] = a[last];/*将比第一个小的移到低端*/ while(first < last && a[first] <= key) { ++first; } a[last] = a[first]; /*将比第一个大的移到高端*/ } a[first] = key;/*枢轴记录到位*/ Qsort(a, low, first-1); Qsort(a, first+1, high); } int main() { int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24}; Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/ for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++) { cout << a[i] << ""; } return 0; }