几种排序算法

排序算法

1 冒泡(Bubble Sort)

图解

算法步骤

  1. 相邻的元素。如果第一个比第二个大,就交换他们两个;
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数;
  3. 针对所有的元素重复以上的步骤,除了最后一个;
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static int *bubbleSort(int input[])
{
static int ret[200];
int temp;
memcpy(ret, input, sizeof(int) * 200);
for (int i = 0; i < 199; i++)
{
for (int j = 0; j < 199 - i; j++)
{
if (ret[j] > ret[j + 1])
{
temp = ret[j];
ret[j] = ret[j + 1];
ret[j + 1] = temp;
}
}
}
return ret;
}

2 选择(Selection Sort)

图解

算法步骤

  1. 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置;
  2. 然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾;
  3. 以此类推,直到所有元素均排序完毕。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static int *selectSort(int input[])
{
static int ret[200];
int temp;
int min;
memcpy(ret, input, sizeof(int) * 200);
for (int i = 0; i < 200; i++)
{
min = i;
for (int j = i; j < 200; j++)
{
if (ret[j] < ret[min])
{
min = j; //mark the min.
}
}
temp = ret[i]; //exchange ret[min] and ret[i]
ret[i] = ret[min];
ret[min] = temp;
}
return ret;
}

3 插入排序(Insertion Sort)

图解

算法步骤

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置后;
  6. 重复步骤2~5。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static int *insertSort(int input[])
{
static int ret[200];
int temp;
int j;
memcpy(ret, input, sizeof(int) * 200);
for (int i = 0; i < 200; i++)
{
temp = ret[i];
for (j = i - 1; j >= 0; j--)
{
if (ret[j] > temp)
{
ret[j + 1] = ret[j];
}
else
{
break;
}
}
ret[j + 1] = temp;
}
return ret;
}

4 希尔排序(Shell Sort)

未完待续

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×